Cod sursa(job #520861)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 10 ianuarie 2011 17:50:05
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,m,x,y,i,ii; char t; unsigned k=0; long long ans=0;
pair<int,int> xx[1300013],xxx[1300013];
int func(pair<int,int> qq[],int gh,int mam)
{pair<int,int> p(gh,mam);
if(qq[n-1]<=p)
 return n;
int i=0,ii=n-1,k;
while(i<ii)
  {k=i+ii>>1;
  if(qq[k]<=p)
   i=k+1;
  else
  ii=k;}
return i;}
int main()
{ifstream q("zc.in");
ofstream w("zc.out");
q>>n>>m;
while(n--)
   {q>>x>>y;
   for(i=x;i<=x+2;++i)
     for(ii=y-2+abs(x-i);ii<=y+2-abs(x-i);++ii)
       if(i||ii)
        {xxx[k].first=i;
        xxx[k++].second=ii;}}
sort(xxx,xxx+k);
xx[0]=xxx[0]; n=1; x=0; y=0;
for(i=1;i<k;++i)
 if(xxx[i]!=xxx[i-1])
  xx[n++]=xxx[i];
for(i=0;i<n;++i)
  {xxx[i].first=xx[i].second;
  xxx[i].second=xx[i].first;}
sort(xxx,xxx+n);
while(m--)
    {q>>t>>k;
    if(t=='N')
     {i=func(xx,x,y);
     y+=k;
     ii=func(xx,x,y);}
    if(t=='S')
     {ii=func(xx,x,y-1);
     y-=k;
     i=func(xx,x,y-1);}
    if(t=='E')
     {i=func(xxx,y,x);
     x+=k;
     ii=func(xxx,y,x);}
    if(t=='V')
     {ii=func(xxx,y,x-1);
     x-=k;
     i=func(xxx,y,x-1);}
    ans+=ii-i;}
w<<ans;
return 0;}