Cod sursa(job #397081)

Utilizator FlorianFlorian Marcu Florian Data 16 februarie 2010 12:45:24
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
using namespace std;
#include<fstream>
#include<algorithm>
#define mk make_pair
#define y second
#define x first
const int MAX_N = 1300007;
pair<int,int> X[MAX_N], Y[MAX_N], T[MAX_N];
long long sol;
int N, M, P, T_LEN;
int dx[13] = { 0, 0, 0, 0, 0, 1, 1, 1, -1, -1, -1, -2, 2 };
int dy[13] = { 0, 1, -2, -1, 2, -1, 1, 0, -1, 1, 0, 0, 0 };
struct cmp
{
	bool operator()(const pair<int, int> a, const pair<int, int> b)
	{
		if(a.x == b.x) return a.y < b.y;
		return a.x < b.x;
	}
};
inline int bs(pair<int,int> A[], int V, int i, int j)
{
	int st = 1, dr = P, m, p1 = 0, p2 = 0;
	while(st <= dr)
	{
		m = (st + dr) >> 1;
		if( A[m].x == V )
		{
			if( A[m].y >= i && (m == 1 || A[m-1].x != V || A[m-1].y < i) ) 
			{
				p1 = m; break;
			}
			else if( A[m].y >= i ) dr = m - 1;
			else st = m + 1;
		}
		else if( A[m].x < V ) st = m + 1;
		else dr = m - 1;
	}
	if(p1 == 0) return 0;
	st = 1; dr = P;
	while(st <= dr)
	{
		m = (st + dr) >> 1;
		if( A[m].x == V )
		{
			if( A[m].y <= j && (m == P || A[m+1].x != V || A[m+1].y > j) ) 
			{
				p2 = m; break;
			}
			else if( A[m].y <= j ) st = m + 1;
			else dr = m - 1;
		}
		else if( A[m].x < V ) st = m + 1;
		else dr = m - 1;
	}
	if(p2 == 0 || p1 > p2) return 0;
	return p2 - p1 + 1;
}
int main()
{
	ifstream in("zc.in"); ofstream out("zc.out");
	in>>N>>M;
	int i,j,a,b, nx, ny;
	char dir; 
	int D;
	for(i = 1; i <= N; ++i)
	{
		in>>a>>b;
		for(j = 0; j < 13; ++j)
		{
			if(a + dx[j] == 0 && b + dy[j] == 0) continue;
			T[++T_LEN] = mk(a + dx[j], b + dy[j]);			
		}
	}
	sort(T+1,T+T_LEN+1,cmp());
	for(i = 1; i <= T_LEN; ++i)
		if( T[i] != T[i-1] )
		{
			X[++P] = T[i];
			Y[P] = mk(T[i].y, T[i].x);
		}
	sort(Y+1,Y+P+1,cmp());
	nx = ny = 0;
	for(;M;--M)
	{
		in>>dir>>D;
		switch(dir)
		{
		case 'N':
			{
				sol += bs(X, nx, ny + 1, ny + D);
				ny += D;
				break;
			}
		case 'E':
			{
				sol += bs(Y, ny, nx + 1, nx + D);
				nx += D;
				break;
			}
		case 'V':
			{
				sol += bs(Y, ny, nx - D, nx - 1);
				nx -= D;
				break;
			}
		case 'S':
			{
				sol += bs(X, nx, ny - D, ny - 1);
				ny -= D;
				break;
			}
		}
	}
	out<<sol<<"\n";
	return 0;
}