Cod sursa(job #1019733)

Utilizator enedumitruene dumitru enedumitru Data 31 octombrie 2013 20:57:54
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
#include<algorithm>
#define MAXCELL 1400000
using namespace std;
ifstream f("zc.in"); ofstream g("zc.out");
struct cell {int x,y;};
int N,M,i,j,x,y,k,nrcel,t1,t2,res;
char c;
pair < int, int > vx[MAXCELL],vy[MAXCELL];
inline int search(pair < int, int > v[MAXCELL], int x, int y)
{   int st=1,dr=nrcel,mid;
    pair < int, int > t;
    t.first=x, t.second=y;
    if(v[nrcel]<=t) return nrcel+1;
    while(st<dr)
    {  	mid=(st+dr)/2;
        if(v[mid]<=t) st=mid+1; else dr=mid;
    }
    return st;
}
int main()
{   f>>N>>M;
    for(i=1; i<=N; ++i)
    {   f>>x>>y;
        for(t1=-2; t1<=2; ++t1)
            for(t2=-2; t2<=2; ++t2)
                if(abs(t1)+abs(t2)<=2 && (x+t1!=0 || y+t2!=0))
                    ++nrcel, vx[nrcel].first=x+t1, vx[nrcel].second=y+t2;
    }
    vx[0].first=vx[1].first-1;
    sort(vx+1,vx+nrcel+1);
    for(i=1; i<=nrcel; ++i)
        if(vx[i].first!=vx[i-1].first || vx[i].second!=vx[i-1].second) vx[++k]=vx[i];
    nrcel=k;
    for(i=1; i<=nrcel; ++i) vy[i].first=vx[i].second, vy[i].second=vx[i].first;
    sort(vy+1, vy+nrcel+1);
    x=y=0;
    for(i=1; i<=M; ++i)
    {   f>>c>>k;
        switch(c)
		{   case 'N': {t1=search(vx,x,y); y+=k; t2=search(vx,x,y);} break;
			case 'S': {t2=search(vx,x,y-1); y-=k; t1=search(vx,x,y-1);} break;
			case 'V': {t2=search(vy,y,x-1); x-=k; t1=search(vy,y,x-1);} break;
			case 'E': {t1=search(vy,y,x); x+=k; t2=search(vy,y,x);} break;
        }
        res += t2 - t1;
    }
    g<<res<<'\n'; g.close(); return 0;
}