Cod sursa(job #1761791)

Utilizator silkMarin Dragos silk Data 22 septembrie 2016 21:05:38
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstdio>
#include <algorithm>
#define NMax 1400000
#define mp make_pair
using namespace std;

pair<int, int> xc[NMax+1];
pair<int, int> yc[NMax+1];
pair<int, int> tx[NMax+1];
pair<int, int> ty[NMax+1];

int dirx[12]={0,1,0,-1,1,1,-1,-1,0,2,0,-2};
int diry[12]={1,0,-1,0,1,-1,1,-1,2,0,-2,0};
int N,M,o;
long long ans;

int Search(pair<int, int> v[], pair<int, int> t)
{
    int st,dr,mid,f=0;

    if( v[o] <= t ) return o+1;
    for(st = 1, dr = o; st <= dr;)
    {
        mid = (st+dr)/2;
        if( v[mid] <= t ) st = mid+1;
        else { f = mid; dr = mid-1; }
    }

    return f;
}

int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);

    int i,j,k,nc,v,x,y,xi,yi;
    char ch;

    scanf("%d %d\n",&N,&M);
    for(nc = 0, i = 1; i <= N; ++i)
    {
        scanf("%d %d\n",&x,&y);
        if( x || y )
        {
            ++nc;
            tx[nc] = mp(x,y);
            ty[nc] = mp(y,x);
        }

        for(k = 0; k < 12; ++k)
        if( ( x+dirx[k] ) || ( y+diry[k] ) )
        {
            ++nc;
            tx[nc] = mp(x+dirx[k],y+diry[k]);
            ty[nc] = mp(y+diry[k],x+dirx[k]);
        }
    }

    sort(tx+1,tx+nc+1);
    sort(ty+1,ty+nc+1);

    for(o = 0, i = 1; i <= nc; )
    {
        for(j = i; tx[i]==tx[j] && j <= nc; ++j);
        xc[++o] = tx[i];
        i = j;
    }

    for(o = 0, i = 1; i <= nc; )
    {
        for(j = i; ty[i]==ty[j] && j <= nc; ++j);
        yc[++o] = ty[i];
        i = j;
    }

    x = y = 0;
    for(i = 1; i <= M; ++i)
    {
        scanf("%c %d\n",&ch,&v);
        xi = x; yi = y;
        if(ch=='N') { y = y+v; nc = Search( xc, mp(x,y) ) - Search( xc, mp(xi,yi) ); }
        else if(ch=='E') { x = x+v; nc = Search( yc, mp(y,x) ) - Search( yc, mp(yi,xi) ); }
        else if(ch=='S') { y = y-v; nc = Search( xc, mp(xi,yi-1) ) - Search( xc, mp(x,y-1) ); }
        else { x = x-v; nc = Search( yc, mp(yi,xi-1) ) - Search( yc, mp(y,x-1) ); }

        ans = ans + nc;
    }

    printf("%lld\n",ans);



return 0;
}