Cod sursa(job #2600830)

Utilizator alex_benescuAlex Ben alex_benescu Data 13 aprilie 2020 12:41:41
Problema Zota & Chidil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<fstream>
#include<algorithm>
  using namespace std;
  ifstream q("zc.in");
  ofstream w("zc.out");
  int n,m,x,y,i,ii; char t; unsigned k=0; long long ans=0;
  pair<int,int> xx[1300000],xxx[1300000];
  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()
  {q>>n>>m;
  while(n--)
     {q>>x>>y;
     for(i=x-2;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);}
      else
      if(t=='S')
       {ii=func(xx,x,y-1);
       y-=k;
       i=func(xx,x,y-1);}
      else
      if(t=='E')
       {i=func(xxx,y,x);
       x+=k;
       ii=func(xxx,y,x);}
      else
      if(t=='V')
       {ii=func(xxx,y,x-1);
       x-=k;
       i=func(xxx,y,x-1);}
      ans+=ii-i;}
  w<<ans;
  return 0;}