Cod sursa(job #1716074)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 11 iunie 2016 22:28:58
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 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;
long long S=0;
struct arr
{
	int x,y;
}NS[1300001],VE[1300001],RNS[1300001],RVE[1300001];
void r(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
        pos++;
    while(f[pos]>='0'&&f[pos]<='9')
        nr=nr*10+f[pos++]-'0';
}
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))
				hi=mi-1,lw=max(lw-2,1);
			else lw=mi+1;
		}
	else
		while(lw<=hi)
		{
			mi=(hi+lw)>>1;
			if(VE[mi].x>x||(VE[mi].x==x&&VE[mi].y>=y))
				hi=mi-1,lw=max(lw-2,1);
			else lw=mi+1;
		}
	return mi;
}
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<=13*N;i+=13)
	{
		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')
			S+=bs(PX+1,PY,1)-bs(PX+lenght+1,PY,1),PX+=lenght;
		else if(way=='S')
			S+=bs(PX+1-lenght,PY,1)-bs(PX+1,PY,1),PX-=lenght;
		else if(way=='E')
			S+=bs(PX,PY+1,2)-bs(PX,PY+lenght+1,2),PY+=lenght;
		else if(way=='V')
			S+=bs(PX,PY+1-lenght,2)-bs(PX,PY+1,2),PY-=lenght;
	}
	printf("%lld",-S);
    return 0;
}