Cod sursa(job #1715948)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 11 iunie 2016 18:24:21
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <cstdio>
#include <algorithm>
#define MAX 8000000
#define INF 2000000005
using namespace std;
  
char f[MAX];
struct arr
{
	int x,y;
}NS[1300001],VE[1300001];
int pos=0,M,N,x,y,L=0;
long long S=0;
bool condVE(arr &a,arr &b)
{
	if(a.x==b.x&&a.y==b.y)
		if(b.x!=INF)
		{
			L++;
			b.x=INF,b.y=INF;
		}
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
bool condNS(arr &a,arr &b)
{
	if(a.x==b.x&&a.y==b.y)
		if(b.x!=INF)
			b.x=INF,b.y=INF;
	return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
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++;
}
void binsearchx(int startx,int endx,int starty,int endy,arr A[])
{
	int mi,hi=13*N-L,lw=1,S1,S2;
	while(lw<=hi)
	{
		mi=(lw+hi)>>1;
		if(A[mi].y>starty||(A[mi].y==starty&&A[mi].x>=startx))
			hi=mi-1,lw=max(1,lw-2);
		else lw=mi+1;
	}
	S1=mi;
	lw=1,hi=13*N-L;
	while(lw<=hi)
	{
		mi=(lw+hi)>>1;
		if(A[mi].y>endy||(A[mi].y==endy&&A[mi].x>=endx))
			hi=mi-1,lw=max(1,lw-2);
		else lw=mi+1;
	}
	S2=mi;
	S+=S2-S1;
}
void binsearchy(int startx,int endx,int starty,int endy,arr A[])
{
	int mi,hi=13*N-L,lw=1,S1,S2;
	while(lw<=hi)
	{
		mi=(lw+hi)>>1;
		if(A[mi].x>=startx||(A[mi].x==startx&&A[mi].y>=starty))
			hi=mi-1,lw=max(1,lw-2);
		else lw=mi+1;
	}
	S1=mi;
	lw=1,hi=13*N-L;
	while(lw<=hi)
	{
		mi=(lw+hi)>>1;
		if(A[mi].x>=endx||(A[mi].x==endx&&A[mi].y>=endy))
			hi=mi-1,lw=max(1,lw-2);
		else lw=mi+1;
	}
	S2=mi;
	S+=S2-S1;
}
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);
		NS[i].x=VE[i].x=x;
		NS[i].y=VE[i].y=y;

		NS[i+1].x=VE[i+1].x=x;
		NS[i+1].y=VE[i+1].y=y-1;
		
		NS[i+2].x=VE[i+2].x=x-1;
		NS[i+2].y=VE[i+2].y=y;
		
		NS[i+3].x=VE[i+3].x=x-1;
		NS[i+3].y=VE[i+3].y=y-1;
		
		NS[i+4].x=VE[i+4].x=x-1;
		NS[i+4].y=VE[i+4].y=y+1;
		
		NS[i+5].x=VE[i+5].x=x-2;
		NS[i+5].y=VE[i+5].y=y;
		
		NS[i+6].x=VE[i+6].x=x+1;
		NS[i+6].y=VE[i+6].y=y;
		
		NS[i+7].x=VE[i+7].x=x+1;
		NS[i+7].y=VE[i+7].y=y+1;
		
		NS[i+8].x=VE[i+8].x=x+1;
		NS[i+8].y=VE[i+8].y=y-1;
		
		NS[i+9].x=VE[i+9].x=x+2;
		NS[i+9].y=VE[i+9].y=y;
		
		NS[i+10].x=VE[i+10].x=x;
		NS[i+10].y=VE[i+10].y=y+2;
		
		NS[i+11].x=VE[i+11].x=x;
		NS[i+11].y=VE[i+11].y=y-2;
		
		NS[i+12].x=VE[i+12].x=x;
		NS[i+12].y=VE[i+12].y=y+1;
	}
	sort(NS+1,NS+13*N+1,condNS);
	sort(NS+1,NS+13*N+1,condNS);
	sort(VE+1,VE+13*N+1,condVE);
	sort(VE+1,VE+13*N+1,condVE);
	int PX=0,PY=0,lenght;
	char way;
	for(int i=1;i<=M;i++)
	{
		rch(way);r(lenght);
		if(way=='N')
		{

			binsearchx(PX,PX+lenght+1,PY,PY,NS);
			PX+=lenght;
		}
		else if(way=='S')
		{
			binsearchx(PX-lenght,PX+1,PY,PY,NS);
			PX-=lenght;
		}
		else if(way=='E')
		{
			binsearchy(PX,PX,PY,PY+lenght+1,VE);
			PY+=lenght;
		}
		else
		{
			binsearchy(PX,PX,PY-lenght,PY+1,VE);
			PY-=lenght;
		}
	}
	printf("%lld",S);
    return 0;
}