Cod sursa(job #493606)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 18 octombrie 2010 20:19:29
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.99 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct pct
{
    int x,y;
};
pct a1[1<<21],b1[1<<21],a[1<<21],b[1<<21];
int dx[]={ 0,-1,-1,-1,-2, 0, 0, 0, 0,+1,+1,+1,+2};
int dy[]={ 0, 0,-1,+1, 0,-1,-2,+1,+2, 0,-1,+1, 0};
int q,n,m,x[1<<17],y[1<<17];
long long tot;
void read()
{
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d\n",&x[i],&y[i]);
}
bool comp1(const pct &A,const pct &B)
{
    if(A.y<B.y)
        return true;
    if(A.y==B.y)
    {
        if(A.x<B.x)
            return true;
    }
    return false;
}
bool comp2(const pct &A,const pct &B)
{
    if(A.x<B.x)
        return true;
    if(A.x==B.x)
    {
        if(A.y<B.y)
            return true;
    }
    return false;
}
void init()
{
    int l1=0,l2=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<14;j++)
            if(!(x[i]+dx[j]==0 && y[i]+dx[j]==0))
            {
                ++q;
                a1[q].x=b1[q].x=x[i]+dx[j];
                a1[q].y=b1[q].y=y[i]+dy[j];
            }
    }
    sort(a1+1,a1+q+1,comp1);
    sort(b1+1,b1+q+1,comp2);
    for(int i=1;i<=q;i++)
    {
        if(!(a1[i].x==a1[i-1].x && a1[i].y==a1[i-1].y))
        {
            ++l1;
            a[l1].x=a1[i].x;
            a[l1].y=a1[i].y;
        }
        if(!(b1[i].x==b1[i-1].x && b1[i].y==b1[i-1].y))
        {
            ++l2;
            b[l2].x=b1[i].x;
            b[l2].y=b1[i].y;
        }
    }
    q=l1;
}
int cb_a_1(int y)
{
    int i=0,pas=1<<21;
    for(i=0;pas;pas>>=1)
        if(i+pas<=q)
            if(a[i+pas].y<y)
                i+=pas;
    return i+1;
}
int cb_b_1(int x)
{
    int i=0,pas=1<<21;
    for(i=0;pas;pas>>=1)
        if(i+pas<=q)
            if(b[i+pas].x<x)
                i+=pas;
    return i+1;
}
int cb_a_2(int y)
{
    int i=0,pas=1<<21;
    for(i=0;pas;pas>>=1)
        if(i+pas<=q)
            if(a[i+pas].y<=y)
                i+=pas;
    return i;
}
int cb_b_2(int x)
{
    int i=0,pas=1<<21;
    for(i=0;pas;pas>>=1)
        if(i+pas<=q)
            if(b[i+pas].x<=x)
                i+=pas;
    return i;
}
int cb_a_3(int pi,int pf,int x)
{
    int i=pi-1,pas=1<<21;
    for(i=pi-1;pas;pas>>=1)
        if(i+pas<=pf)
            if(a[i+pas].x<x)
                i+=pas;
    return i+1;
}
int cb_b_3(int pi,int pf,int y)
{
    int i=pi-1,pas=1<<21;
    for(i=pi-1;pas;pas>>=1)
        if(i+pas<=pf)
            if(b[i+pas].y<y)
                i+=pas;
    return i+1;
}
void move(int px,int py,char dir,unsigned int sp)
{
    int i1,i2,j1,j2,pfx,pfy;
    if(dir=='N')
    {
        pfx=px;
        pfy=py+sp;
        i1=cb_b_1(px);
        i2=cb_b_2(px);
        j1=cb_b_3(i1,i2,py);
        j2=cb_b_3(i1,i2,pfy+1);
        tot+=(long long)j2-j1;
        return;
    }
    if(dir=='E')
    {
        pfx=px+sp;
        pfy=py;
        i1=cb_a_1(py);
        i2=cb_a_2(py);
        j1=cb_a_3(i1,i2,px);
        j2=cb_a_3(i1,i2,pfx+1);
        tot+=(long long)j2-j1;
        return;
    }
    if(dir=='S')
    {
        pfx=px;
        pfy=py-sp;
        i1=cb_b_1(px);
        i2=cb_b_2(px);
        j1=cb_b_3(i1,i2,pfy);
        j2=cb_b_3(i1,i2,py+1);
        tot+=(long long)j2-j1;
        return;
    }
    if(dir=='V')
    {
        pfx=px-sp;
        pfy=py;
        i1=cb_a_1(py);
        i2=cb_a_2(py);
        j1=cb_a_3(i1,i2,pfx);
        j2=cb_a_3(i1,i2,px+1);
        tot+=(long long)j2-j1;
        return;
    }
}
void solve()
{
    int px=0,py=0;
    char dir;
    unsigned int sp;
    px=py=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%c %u\n",&dir,&sp);
        move(px,py,dir,sp);
        if(dir=='N')
            py+=sp;
        if(dir=='E')
            px+=sp;
        if(dir=='S')
            py-=sp;
        if(dir=='V')
            px-=sp;

    }
    printf("%lld",tot);
}
int main()
{
    read();
    init();
    solve();
    return 0;
}