Cod sursa(job #592669)

Utilizator Smaug-Andrei C. Smaug- Data 29 mai 2011 20:00:21
Problema Zota & Chidil Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>
#include <utility>
#include <cctype>
using namespace std;

#define MAXN 100000

int bs(pair<int,int> *v, int l, int r, pair<int,int> key){

  int mid;

  while(l<=r){
    mid=((r-l)>>1)+l;
    if(v[mid]<key)
      l=mid+1;
    else
      r=mid-1;
  }

  return l;
}

int main(){

  freopen("zc.in", "r", stdin);
  freopen("zc.out", "w", stdout);

  int N, M, i, a, b, j, k, d[5]={0,1,2,1,0}, cnt, x, y;
  static pair<int,int> X[16*MAXN+10], Y[16*MAXN+10];
  char c;
  long long dust;

  cnt=0;

  scanf("%d%d", &N, &M);
  for(i=0; i<N; i++){
    scanf("%d%d", &a, &b);
    
    for(j=a-2; j<=a+2; j++)
      for(k=b-d[j+2-a]; k<=b+d[j+2-a]; k++)
	if(j||k)
	  X[cnt++]=make_pair(j,k);
  }

  sort(X, X+cnt);

  N=1;
  for(i=1; i<cnt; i++)
    if(X[i]!=X[i-1])
      X[N++]=X[i];
    
  for(i=0; i<N; i++)
    Y[i]=make_pair(X[i].second, X[i].first);

  sort(Y, Y+N);
  
  x=0; y=0; dust=0;

  for(i=0; i<M; i++){
    c=' ';
    while(isspace(c))
      scanf("%c", &c);
    scanf("%d", &k);

    if(c=='N'){
      a=bs(X, 0, N-1, make_pair(x,y));
      y+=k;
      b=bs(X, 0, N-1, make_pair(x,y));
      if(X[b]!=make_pair(x,y))
	b--;	
    }
    else if(c=='S'){
      b=bs(X, 0, N-1, make_pair(x,y));
      if(X[b]!=make_pair(x,y))
	b--;
      y-=k;
      a=bs(X, 0, N-1, make_pair(x,y));
    }
    else if(c=='E'){
      a=bs(Y, 0, N-1, make_pair(y,x));
      x+=k;
      b=bs(Y, 0, N-1, make_pair(y,x));
      if(Y[b]!=make_pair(y,x))
	b--;
    }
    else if(c=='V'){
      b=bs(Y, 0, N-1, make_pair(y,x));
      if(Y[b]!=make_pair(y,x))
	b--;
      x-=k;
      a=bs(Y, 0, N-1, make_pair(y,x));
    }
    //printf("%d\n", abs(a-b));
    dust+=b-a+1;

  }

  printf("%lld\n", dust);

  return 0;
  
}