Cod sursa(job #494126)

Utilizator indestructiblecont de teste indestructible Data 20 octombrie 2010 20:04:38
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 900005
#define INF 2000000100
#define pb push_back
using namespace std;
int n,m,r,f,g,D[NMAX],E[NMAX],dir,pasi,px,py,rez;
int dlin[]={0,0,0,1,1,2,-1,-1,-2};
int dcol[]={0,-2,2,-1,1,0,-1,1,0};
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
struct pct { int a,b; };
pct A[NMAX];
vector <int> B[NMAX],C[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,j,x,y;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d\n",&x,&y);
		for (j=0; j<9; j++)
		{
			A[++r].a=y+dlin[j],A[r].b=x+dcol[j];
			if (A[r].a==0 && A[r].b==0) r--;
		}
	}
}
bool comp1(pct x,pct y)
{
	return x.a<y.a || (x.a==y.a && x.b<y.b);
}
bool comp2(pct x,pct y)
{
	return x.b<y.b || (x.b==y.b && x.a<y.a);
}
void prepare()
{
	sort(A+1,A+r+1,comp1);
	A[0].a=-INF;
	int i,poz=0;
	for (i=1; i<=r; i++)
		if (A[i].a!=A[i-1].a || A[i].b!=A[i-1].b)
			A[++poz]=A[i];
	r=poz;
	for (i=1; i<=r; i++)
	{
		if (A[i].a!=A[i-1].a)
			D[++f]=A[i].a;
		B[f].pb(A[i].b);
	}
	sort(A+1,A+r+1,comp2);
	for (i=1; i<=r; i++)
	{
		if (A[i].b!=A[i-1].b)
			E[++g]=A[i].b;
		C[g].pb(A[i].a);
	}
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
int cauta1(int st,int dr,int x)
{
	if (x==-1) return 0;
	int i1,i2,step,step1;
	for (step=1; step<=C[x].size(); step<<=1);
	step1=step;
	for (i1=-1; step; step>>=1)
		if (i1+step<C[x].size() && C[x][i1+step]<st)
			i1+=step;
	i1++;
	step=step1;
	for (i2=-1; step; step>>=1)
		if (i2+step<C[x].size() && C[x][i2+step]<=dr)
			i2+=step;
	if (i1>i2) return 0;
	return i2-i1+1;
}
int cauta2(int st,int dr,int x)
{
	if (x==-1) return 0;
	int i1,i2,step,step1;
	for (step=1; step<=B[x].size(); step<<=1);
	step1=step;
	for (i1=-1; step; step>>=1)
		if (i1+step<C[x].size() && B[x][i1+step]<st)
			i1+=step;
	i1++;
	step=step1;
	for (i2=-1; step; step>>=1)
		if (i2+step<C[x].size() && B[x][i2+step]<=dr)
			i2+=step;
	if (i1>i2) return 0;
	return i2-i1+1;
}
int cb1(int val)
{
	int i=0,step;
	for (step=1; step<=g; step<<=1)
		if (i+step<=g && E[i+step]<=val)
			i+=step;
	if (E[i]==val) return i;
	return -1;
}
int cb2(int val)
{
	int i=0,step;
	for (step=1; step<=f; step<<=1)
		if (i+step<=f && D[i+step]<=val)
			i+=step;
	if (D[i]==val) return i;
	return -1;
}
void solve()
{
	int i,x_n,y_n;
	char x;
	for (i=1; i<=m; i++)
	{
		scanf("%c",&x);
		if (x=='N') dir=0;
		if (x=='S') dir=1;
		if (x=='V') dir=2;
		if (x=='E') dir=3;
		scanf("%d\n",&pasi);
		x_n=px+pasi*dx[dir];
		y_n=py+pasi*dy[dir];
		if (dir==0 || dir==1)
			rez+=cauta1(min(px+dx[dir],x_n),max(px+dx[dir],x_n),cb2(py));
		if (dir==2 || dir==3)
			rez+=cauta2(min(py+dy[dir],y_n),max(py+dy[dir],y_n),cb1(px));
		px=x_n; py=y_n;
	}
}
int main()
{
	freopen("zc.in","r",stdin);
	freopen("zc.out","w",stdout);
	read();
	prepare();
	solve();
	printf("%d\n",rez);
	return 0;
}