Cod sursa(job #1716299)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 12 iunie 2016 14:01:14
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <cstdio>
#include <algorithm>
#define MAX 8000000
#define INF 2000000005
using namespace std;
  
char f[MAX],way;
int pos=0,M,N,x,y,L=0,PX=0,PY=0,lenght,l=0,l1=0,l2=0,negative,positive,v1[13]={0,-2,-1,-1,-1,0,0,0,0,1,1,1,2},v2[13]={0,0,-1,0,1,-2,-1,1,2,-1,0,1,0};
long long S=0;
struct arr
{
	int x,y;
}NS[1300001],VE[1300001];
void r(int &nr)
{
    nr=0;
	int sign=1;
    while(f[pos]<'0'||f[pos]>'9')
	{
		if(f[pos]=='-') sign=0;
        pos++;
	}
    while(f[pos]>='0'&&f[pos]<='9')
        nr=nr*10+f[pos++]-'0';
	if(sign==0)
		nr=-nr;
}
void rch(char &ch)
{
    while(f[pos]<'A'||f[pos]>'Z')
        pos++;
	ch=f[pos];
	pos++;
}
bool condVE(arr a,arr b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool condNS(arr a,arr b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int bs(int x,int y,int val)
{
	int mi,lw=1,hi=l;
	if(val==1)
	{
		while(lw<=hi)
		{
			mi=(hi+lw)>>1;
			if(NS[mi].y<y||(NS[mi].y==y&&NS[mi].x<=x))
				lw=mi+1;
			else hi=mi-1;
		}
	}
	else
	{
		while(lw<=hi)
		{
			mi=(hi+lw)>>1;
			if(VE[mi].x<x||(VE[mi].x==x&&VE[mi].y<=y))
				lw=mi+1;
			else hi=mi-1;
		}
	}
	return lw;
}
int main()
{
    freopen("zc.in","r",stdin);
	freopen("zc.out","w",stdout);
    fread(f,1,MAX,stdin);
	r(N);r(M);
	for(int i=1;i<=N;i++)
	{
		r(y);r(x);
		for(int j=0;j<13;j++)
		{
			NS[++L].x=x+v1[j];
			NS[L].y=y+v2[j];
		}
	}
	sort(NS+1,NS+1+L,condNS);
	for(int i=1;i<=L;i++)
		if(NS[i].x!=NS[i-1].x||NS[i].y!=NS[i-1].y)
		{
			++l1;
			NS[l1]=VE[l1]=NS[i];
		}
	l=l1;
	sort(VE+1,VE+1+l,condVE);
	for(int i=1;i<=M;i++)
	{
		rch(way);r(lenght);
		if(way=='N')
		{
			negative=bs(PX,PY,1);
			positive=bs(PX+lenght,PY,1);
			PX+=lenght;
		}
		else if(way=='S')
		{
			negative=bs(PX-lenght-1,PY,1);
			positive=bs(PX-1,PY,1);
			PX-=lenght;
		}
		else if(way=='E')
		{
			negative=bs(PX,PY,2);
			positive=bs(PX,PY+lenght,2);
			PY+=lenght;
		}
		else if(way=='V')
		{
			negative=bs(PX,PY-lenght-1,2);
			positive=bs(PX,PY-1,2);
			PY-=lenght;
		}
		S+=positive-negative;
	}
	printf("%lld",S);
    return 0;
}