Cod sursa(job #1716161)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 12 iunie 2016 01:48:17
Problema Zota & Chidil Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 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;
long long S=0;
struct arr
{
	int x,y;
}NS[1300001],VE[1300001],RNS[1300001],RVE[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=-2;j<=2;j++)
			for(int k=-2;k<=2;k++)
				if(abs(j)+abs(k)<=2)
				{
					RNS[++L].x=x+j,RNS[L].y=y+k;
					RVE[L].x=x+j,RVE[L].y=y+k;
				}
	}
	sort(RNS+1,RNS+1+L,condNS);
	sort(RVE+1,RVE+1+L,condVE);
	for(int i=1;i<=L;i++)
	{
		if(RNS[i].x!=RNS[i-1].x||RNS[i].y!=RNS[i-1].y)
			NS[++l1]=RNS[i];
		if(RVE[i].x!=RVE[i-1].x||RVE[i].y!=RVE[i-1].y)
			VE[++l2]=RVE[i];
	}
	l=l1;
	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;
}