Cod sursa(job #494189)

Utilizator indestructiblecont de teste indestructible Data 20 octombrie 2010 22:08:16
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 1300005
#define INF 2000000100
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define a first
#define b second
using namespace std;
int n,m,r,f,g,dir,pasi,px,py,rez;
int dlin[]={2,1,1,1,0,0,0,0,0,-1,-1,-1,-2};
int dcol[]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
vector <pii> A,G;
vector <int> B[NMAX],C[NMAX],D,E;
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<13; j++)
			if (x+dlin[j]!=0 || y+dcol[j]!=0)
				A.pb(mp(x+dlin[j],y+dcol[j]));
	}
}
bool comp1(pii x,pii y)
{
	return x.a<y.a || (x.a==y.a && x.b<y.b);
}
bool comp2(pii x,pii y)
{
	return x.b<y.b || (x.b==y.b && x.a<y.a);
}
void prepare()
{
	sort(A.begin(),A.end(),comp1);
	int i;
	for (i=0; i<A.size(); i++)
		if (i>0 && (A[i].a!=A[i-1].a || A[i].b!=A[i-1].b))
			G.pb(mp(A[i].a,A[i].b));
	for (i=0; i<G.size(); i++)
	{
		if (i==1 || (i>1 && G[i].a!=G[i-1].a))
			D.pb(G[i].a),f++;
		B[f].pb(G[i].b);
	}
	sort(G.begin(),G.end(),comp2);
	for (i=0; i<G.size(); i++)
	{
		if (i==1 || (i>1 && G[i].b!=G[i-1].b))
			E.pb(G[i].b),g++;
		C[g].pb(G[i].a);
	}
	A.clear(); G.clear();
}
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<B[x].size() && B[x][i1+step]<st)
			i1+=step;
	i1++;
	step=step1;
	for (i2=-1; step; step>>=1)
		if (i2+step<B[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<=r; step<<=1) ;
	for (i=0; step; step>>=1)
		if (i+step<=g && E[i+step-1]<=val)
			i+=step;
	if (E[i-1]==val) return i;
	return -1;
}
int cb2(int val)
{
	int i=0,step;
	for (step=1; step<=f; step<<=1) ;
	for (i=0; step; step>>=1)
		if (i+step<=f && D[i+step-1]<=val)
			i+=step;
	if (D[i-1]==val) return i;
	return -1;
}
void solve()
{
	int i,x_n,y_n;
	char x;
	for (i=1; i<=m; i++)
	{
		scanf("%c",&x);
		scanf("%d\n",&pasi);
		if (x=='N') dir=0;
		if (x=='S') dir=1;
		if (x=='V') dir=2;
		if (x=='E') dir=3;
		x_n=px+pasi*dx[dir];
		y_n=py+pasi*dy[dir];
		if (dir==0 || dir==1)
			rez+=cauta2(min(py+dy[dir],y_n),max(py+dy[dir],y_n),cb2(px));
		if (dir==2 || dir==3)
			rez+=cauta1(min(px+dx[dir],x_n),max(px+dx[dir],x_n),cb1(py));
		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;
}