Cod sursa(job #517812)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 29 decembrie 2010 22:25:09
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm 100001
#define abs(a) ((a)<0?-(a):(a))
pair<int,int> V1[13*Nm],V2[13*Nm];
int n;

int bs(pair<int,int> V[], int f, int s)
{
    pair<int,int> p(f,s);
    if(V[n-1]<=p)
        return n;

    int i=0,j=n-1,k;

    while(i<j)
    {
        k=i+j>>1;
        if(V[k]<=p)
            i=k+1;
        else
            j=k;
    }
    return i;
}

int main()
{
    char d;
    int m,x,y,i,j;
    unsigned k=0;
    long long ans=0;

    freopen("zc.in","r",stdin);
    scanf("%d%d",&n,&m);
    while(n--)
    {
        scanf("%d%d",&x,&y);
        for(i=x-2;i<=x+2;++i)
            for(j=y-2+abs(x-i);j<=y+2-abs(x-i);++j)
                if(i || j)
                {
                    V2[k].first=i;
                    V2[k++].second=j;
                }
    }

    sort(V2,V2+k);
    V1[0]=V2[0]; n=1;
    for(i=1;i<k;++i)
        if(V2[i]!=V2[i-1])
            V1[n++]=V2[i];
    for(i=0;i<n;++i)
    {
        V2[i].first=V1[i].second;
        V2[i].second=V1[i].first;
    }
    sort(V2,V2+n);

    x=0; y=0;
    scanf(" ");
    while(m--)
    {
        scanf("%c %u\n",&d,&k);
        if(d=='N')
        {
            i=bs(V1,x,y);
            y+=k;
            j=bs(V1,x,y);
        }
        if(d=='S')
        {
            j=bs(V1,x,y-1);
            y-=k;
            i=bs(V1,x,y-1);
        }
        if(d=='E')
        {
            i=bs(V2,y,x);
            x+=k;
            j=bs(V2,y,x);
        }
        if(d=='V')
        {
            j=bs(V2,y,x-1);
            x-=k;
            i=bs(V2,y,x-1);
        }
        ans+=j-i;
    }

    freopen("zc.out","w",stdout);
    printf("%lld\n",ans);

    return 0;
}