Cod sursa(job #520236)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 7 ianuarie 2011 16:27:51
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

int v[1300001][2],v2[1300001][2],ind[1300001],n,m;

inline int cmp(int i,int j)
{
    if (v[i][0]==v[j][0]) return v[i][1]<v[j][1];
    return v[i][0]<v[j][0];
}

inline int cmp2(int i,int j)
{
    if (v[i][1]==v[j][1]) return v[i][0]<v[j][0];
    return v[i][1]<v[j][1];
}

inline int comp(int a,int b,int c)
{
    if (v[a][0]==b) return v[a][1]<c;
    return v[a][0]<b;
}

inline int comp2(int a,int b,int c)
{
    if (v2[a][1]==c) return v2[a][0]<b;
    return v2[a][1]<c;
}

int bs_ns_l(int l,int r,int key1,int key2)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (comp2(mid,key1,key2)) l=mid+1;
        else r=mid;
    }
    mid=(l+r)/2;
    if (comp2(mid,key1,key2)) ++mid;
    return mid;
}

int bs_ns_r (int l,int r,int key1,int key2)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (comp2(mid,key1,key2)||((v[mid][0]==key1)&&(v[mid][1]==key2))) l=mid+1;
        else r=mid;
    }
    mid=(l+r)/2;
    if (!comp2(mid,key1,key2)&&((v[mid][0]!=key1)||(v[mid][1]!=key2))) --mid;
    return mid;
}

int bs_we_l(int l,int r,int key1,int key2)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (comp(mid,key1,key2)) l=mid+1;
        else r=mid;
    }
    mid=(l+r)/2;
    if (comp(mid,key1,key2)) ++mid;
    return mid;
}

int bs_we_r (int l,int r,int key1,int key2)
{
    int mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (comp(mid,key1,key2)||((v[mid][0]==key1)&&(v[mid][1]==key2))) l=mid+1;
        else r=mid;
    }
    mid=(l+r)/2;
    if (!comp(mid,key1,key2)&&((v[mid][0]!=key1)||(v[mid][1]!=key2))) --mid;
    return mid;
}

int main()
{
    int e,i,n,m,c=0,x,x2,y,y2,s=0;
    char d;
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=n;++i)
    {
        scanf("%d %d\n",&y,&x);
        v[13*i-12][0]=x;v[13*i-12][1]=y;
        v[13*i-11][0]=x+2;v[13*i-11][1]=y;
        v[13*i-10][0]=x+1;v[13*i-10][1]=y-1;
        v[13*i-9][0]=x+1;v[13*i-9][1]=y;
        v[13*i-8][0]=x+1;v[13*i-8][1]=y+1;
        v[13*i-7][0]=x;v[13*i-7][1]=y-2;
        v[13*i-6][0]=x;v[13*i-6][1]=y-1;
        v[13*i-5][0]=x;v[13*i-5][1]=y+1;
        v[13*i-4][0]=x;v[13*i-4][1]=y+2;
        v[13*i-3][0]=x-1;v[13*i-3][1]=y-1;
        v[13*i-2][0]=x-1;v[13*i-2][1]=y;
        v[13*i-1][0]=x-1;v[13*i-1][1]=y+1;
        v[13*i][0]=x-2;v[13*i][1]=y;
    }
    n*=13;
    for (i=1;i<=n;++i) ind[i]=i;
    sort(ind+1,ind+n+1,cmp);
    for (i=1;i<=n;++i)
    {
        v2[i][0]=v[ind[i]][0];
        v2[i][1]=v[ind[i]][1];
    }
    for (i=1;i<=n;++i)
    {
        v[i][0]=v2[i][0];
        v[i][1]=v2[i][1];
    }
    for (i=1;i<=n;++i)
        if (((v[i][0]!=v[i-1][0])||(v[i][1]!=v[i-1][1]))&&((v[i][0]!=0)||(v[i][1]!=0)))
        {
            ++c;
            v[c][0]=v[i][0];
            v[c][1]=v[i][1];
        }
    n=c;
    for (i=1;i<=n;++i) ind[i]=i;
    sort(ind+1,ind+n+1,cmp2);
    for (i=1;i<=n;++i)
    {
        v2[i][0]=v[ind[i]][0];
        v2[i][1]=v[ind[i]][1];
    }
    x=0;y=0;
    for (i=1;i<=m;++i)
    {
        scanf("%c %d\n",&d,&e);
        if (d=='N')
        {
            x2=x+e;
            y2=y;
            s+=bs_ns_r(1,n,x2,y2)-bs_ns_l(1,n,x,y)+1;
            x=x2;
        }
        else if (d=='S')
        {
            x2=x-e;
            y2=y;
            s+=bs_ns_r(1,n,x,y)-bs_ns_l(1,n,x2,y2)+1;
            x=x2;
        }
        else if (d=='E')
        {
            x2=x;
            y2=y+e;
            s+=bs_we_r(1,n,x2,y2)-bs_we_l(1,n,x,y)+1;
            y=y2;
        }
        else
        {
            x2=x;
            y2=y-e;
            s+=bs_we_r(1,n,x,y)-bs_we_l(1,n,x2,y2)+1;
            y=y2;
        }
    }
    printf("%d",s);
    return 0;
}