Cod sursa(job #282771)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 18 martie 2009 10:52:39
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define INF 2000000001
#define pb push_back
using namespace std;
int dx[]={-2,-1,-1,-1, 0, 0,0,0,0, 1,1,1,2};
int dy[]={ 0,-1, 0, 1,-2,-1,0,1,2,-1,0,1,0};
const int D=13;
int n,m,Q,i,j,k,xx,yy,q,dis,sol,x[100005],y[100005];
int cx[1300005],cy[1300005],lx,ly,qx[400000],qy[400000];
vector <int> vx[500000],vy[500000];
char dir;

int head_sch(int n,int v,int xy){
  int low=1,mid,cc,high=n;
  while (low < high){
    mid=(low+high)>>1;
    cc=(xy==0)?cx[mid]:cy[mid];
    if (cc<v)low=mid+1;else high=mid;
  }
return low;
}

int x_sch(int line,int v,int high){
  int low=0,mid,cc;
  while (low < high){
    mid=(low+high)>>1;
    cc=vx[line][mid];
    if (cc<v)low=mid+1; else high=mid;
  }
return low;
}
  
int y_sch(int col ,int v,int high){
  int low=0,mid,cc;
  while (low < high){
    mid=(low+high)>>1;
    cc=vy[col][mid];
    if (cc<v)low=mid+1; else high=mid; 
  }
return low;
}

int get_on_x(int line,int c1,int c2){
  int k,k1,k2;
  k=head_sch(lx,line,0);
  if (cx[k]!=line||qx[k]==0)return 0;
  k1=x_sch(k,c1,qx[k]);
  k2=x_sch(k,c2,qx[k]);
  if (vx[k][k2]!=c2||k2==qx[k])k2--;
  return k2-k1+1;
}

int get_on_y(int col ,int l1,int l2){
  int k,k1,k2;
  k=head_sch(ly,col,1);
  if (cy[k]!=col||qy[k]==0)return 0;
  k1=y_sch(k,l1,qy[k]);
  k2=y_sch(k,l2,qy[k]);
  if (vy[k][k2]!=l2||k2==qy[k])k2--;
  return k2-k1+1;
}

int main(){
  freopen("zc.in","r",stdin); freopen("zc.out","w",stdout);
  scanf("%d %d",&n,&Q); 
  for (i=1;i<=n;++i){
    scanf("%d %d\n",&y[i],&x[i]);
    for (j=0;j<D;++j){
      xx = x[i] + dx[j]; yy = y[i] + dy[j];
      if (xx==0&&yy==0)continue;
      ++q;cx[q]=xx;cy[q]=yy;
    }
  }
  sort(cx+1,cx+q+1);
  sort(cy+1,cy+q+1);
  //initializare coordonate x si y folosite
  lx=1;ly=1;//cx[0]=-INF;cy[0]=-INF;
  for (i=2;i<=q;++i)if (cx[i]!=cx[i-1])cx[++lx]=cx[i];
  for (i=2;i<=q;++i)if (cy[i]!=cy[i-1])cy[++ly]=cy[i];
  for (i=1;i<=n;++i)
    for (j=0;j<D;++j){
      xx = x[i] + dx[j];
      yy = y[i] + dy[j];
      if (xx==0&&yy==0)continue;
      k=head_sch(lx,xx,0);
      vx[k].pb(yy);
      k=head_sch(ly,yy,1);
      vy[k].pb(xx);
    }
  //sortare liste de coordonate
  for (i=1;i<=lx;++i){
    sort(vx[i].begin(),vx[i].end());
    qx[i]=0;m=vx[i].size();
    for (j=1;j<m;++j)if (vx[i][j]!=vx[i][j-1])vx[i][++qx[i]]=vx[i][j];
    qx[i]++;
  }
  for (i=1;i<=ly;++i){
    sort(vy[i].begin(),vy[i].end());
    qy[i]=0;m=vy[i].size();
    for (j=1;j<m;++j)if (vy[i][j]!=vy[i][j-1])vy[i][++qy[i]]=vy[i][j];
    qy[i]++;
  }
  //aplicarea traseului
  xx=0;yy=0;
  for (;Q>0;--Q){
    scanf("%c %d\n",&dir,&dis);
    if (dir=='E'){
      sol+=get_on_x(xx,yy+1,yy+dis);
      yy+=dis;
    }
    if (dir=='V'){
      sol+=get_on_x(xx,yy-dis,yy-1);
      yy-=dis;
    }
    if (dir=='S'){
      sol+=get_on_y(yy,xx-dis,xx-1);
      xx-=dis;
    }
    if (dir=='N'){
      sol+=get_on_y(yy,xx+1,xx+dis);
      xx+=dis;
    }
  }
  printf("%d\n",sol);
}