Cod sursa(job #2841068)

Utilizator daria0123daria ghitescu daria0123 Data 29 ianuarie 2022 11:42:24
Problema Zota & Chidil Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct punct
{
 int x, y;
};

int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int dy[13] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};
punct ox[1300005], oy[1300005];
int n, m, l=0;
long long ans = 0;
punct chidil;

inline bool cmp (punct a, punct b)
{
    return a.y<b.y || (a.y==b.y && a.x<b.x);
}

inline bool cmp2 (punct a, punct b)
{
    return !cmp(b, a);
}

inline int bs(punct *v, punct val)
{
    int st=1, dr=l, mid, last=0;
    while (st<=dr)
    {
        mid=(st+dr)/2;
        if(cmp2(v[mid], val))
        {
            last=mid;
            st=mid+1;
        }
        else dr=mid-1;
    }
    return last;
}

inline punct transform(punct x) {
    punct y;
    y.x = x.y;
    y.y = x.x;
    return y;
}

int main()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        int x, y;
        scanf("%d %d", &y, &x);
        for(int j=0; j<13; j++)
        {
            l++;
            ox[l].x = x+dx[j];
            ox[l].y=y+dy[j];

            oy[l].y = x+dx[j];
            oy[l].x=y+dy[j];

        }
    }

    sort ( ox+1, ox+1+l, cmp);
    sort ( oy+1, oy+1+l , cmp);

    for(int i=1; i<=m; i++)
    {
        punct dest;
        char dir;
        int dist;
        scanf(" %c %d", &dir, &dist);

        if(dir=='S')
        {
            dest=chidil;
            dest.x-=dist;
            ans+= bs(ox, chidil)-bs(ox, dest);
        }
        else if (dir=='N')
        {
            dest=chidil;
            dest.x+=dist;
            ans += bs(ox, dest) - bs(ox, chidil);

        }
        else if(dir=='V')
        {
            dest=chidil;
            dest.y-=dist;
            ans+=bs(oy, transform(chidil))-bs(oy, transform(dest));
        }
        else
        {
            dest=chidil;
            dest.y+=dist;
            ans+=bs(oy, transform(dest))-bs(oy, transform(chidil));
        }
        chidil = dest;

    }
    printf("%lld\n", ans);
    return 0;
}