Cod sursa(job #1403348)

Utilizator akaprosAna Kapros akapros Data 27 martie 2015 11:09:04
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.19 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define Nmax 100005
#define mod 666013
using namespace std;
int i,j,n,m,x,l,c,p,sol;
char ch;
vector < int >V[mod];
int ap(int x)
{
    int i;
    for (i=0;i<V[x%mod].size();i++)
    if (V[x%mod][i]==x) return 1;
    return 0;
}
struct nod
{
    int x;
    int y;
} v[Nmax],w[Nmax];
int cb1(int l)
{
    int st=1,dr=n,mij=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij].x>c && w[mij-1].x-c<-2) return mij;
        if (v[mij].x-l<-2 && v[mij+1].x>l) return mij+1;
        if (v[mij].x<l && v[mij].x-l>=-2 && v[mij-1].x-l<-2) return mij;
        if (v[mij].x<l) st=mij+1;
        else dr=mij-1;
    }
    return 0;
}

int cb2(int c)
{
    int st=1,dr=n,mij=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (w[mij].y>=c && w[mij-1].y-c<-2) return mij;
        if (w[mij].y-c<-2 && w[mij+1].y>c) return mij+1;
        if (w[mij].y<=c && w[mij].y-c>=-2 && w[mij-1].y-c<-2) return mij;
        if (w[mij].y<c) st=mij+1;
        else dr=mij-1;
    }
    return 0;
}

int cmp1(const nod a,const nod b)
{
    if (a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
int cmp2(const nod a,const nod b)
{
    if (a.y==b.y) return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    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",&v[i].x,&v[i].y);
        w[i]=v[i];
    }
    l=0; c=0;
    sort(v+1,v+n+1,cmp1);
    sort(w+1,w+n+1,cmp2);
    for (i=1;i<=m;i++)
    {
        scanf("%c %d\n",&ch,&x);
        if (ch=='N' || ch=='S')
        {
            if (i==3)
            i=i;
            p=cb1(l);
            while (abs(v[p].x-l)<=2 && p<=n && p>0)
            {
                //if (abs(v[p].y-c)<=2)
                {
                    if (abs(v[p].x-l)==0)
                    {
                        if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
                        {sol++; V[v[p].y%mod].push_back(v[p].y);}
                        if (v[p].y-1<=c+x && v[p].y-1>=c && !ap(v[p].y-1))
                        {sol++; V[(v[p].y-1)%mod].push_back(v[p].y-1);}
                        if (v[p].y+1<=c+x && v[p].y+1>=c && !ap(v[p].y+1))
                        {sol++; V[(v[p].y+1)%mod].push_back(v[p].y+1);}
                        if (v[p].y-2<=c+x && v[p].y-2>=c && !ap(v[p].y-2))
                        {sol++; V[(v[p].y-2)%mod].push_back(v[p].y-2);}
                        if (v[p].y+2<=c+x && v[p].y+2>=c && !ap(v[p].y+2))
                        {sol++; V[(v[p].y-2)%mod].push_back(v[p].y-2);}
                    }
                    if (abs(v[p].x-l)==1)
                    {
                         if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
                        {sol++; V[v[p].y%mod].push_back(v[p].y);}
                        if (v[p].y-1<=c+x && v[p].y-1>=c && !ap(v[p].y-1))
                        {sol++; V[(v[p].y-1)%mod].push_back(v[p].y-1);}
                        if (v[p].y+1<=c+x && v[p].y+1>=c && !ap(v[p].y+1))
                        {sol++; V[(v[p].y+1)%mod].push_back(v[p].y+1);}
                    }else
                    if (v[p].y<=c+x && v[p].y>=c && !ap(v[p].y))
                    {sol++; V[v[p].y%mod].push_back(v[p].y);}
                }
                p++;
            }
            if (ch=='N') c+=x;
            else c-=x;
        } else
        {
            p=cb2(c);
            while (abs(v[p].y-c)<=2 && p<=n && p>0)
            {
               // if (abs(v[p].x-l)<=2)
                {
                    if (abs(v[p].y-c)==0)
                    {
                        if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
                        {sol++; V[v[p].x%mod].push_back(v[p].x);}
                        if (v[p].x-1<=l+x && v[p].x-1>=l && !ap(v[p].x-1))
                        {sol++; V[(v[p].x-1)%mod].push_back(v[p].x-1);}
                        if (v[p].x+1<=l+x && v[p].x+1>=l && !ap(v[p].x+1))
                        {sol++; V[(v[p].x+1)%mod].push_back(v[p].x+1);}
                        if (v[p].x-2<=l+x && v[p].x-2>=l && !ap(v[p].x-2))
                        {sol++; V[(v[p].x-2)%mod].push_back(v[p].x-2);}
                        if (v[p].x+2<=l+x && v[p].x+2>=l && !ap(v[p].x+2))
                        {sol++; V[(v[p].x-2)%mod].push_back(v[p].x-2);}
                    }
                    if (abs(v[p].y-c)==1)
                    {
                        if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
                        {sol++; V[v[p].x%mod].push_back(v[p].x);}
                        if (v[p].x-1<=l+x && v[p].x-1>=l && !ap(v[p].x-1))
                        {sol++; V[(v[p].x-1)%mod].push_back(v[p].x-1);}
                        if (v[p].x+1<=l+x && v[p].x+1>=l && !ap(v[p].x+1))
                        {sol++; V[(v[p].x+1)%mod].push_back(v[p].x+1);}
                    }else
                    if (v[p].x<=l+x && v[p].x>=l && !ap(v[p].x))
                    {sol++; V[v[p].x%mod].push_back(v[p].x);}
                }
                p++;
            }
            if (ch=='E') l+=x;
            else l-=x;
        }
    }
    printf("%d",sol);
    return 0;
}