Cod sursa(job #494083)

Utilizator ooctavTuchila Octavian ooctav Data 20 octombrie 2010 18:23:41
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

const int NMAX = 100005;
const int PUNCTE = 13;

int N, M, REZ;
pair<int, int> caplin[NMAX * 13], capcol[NMAX * 13];
int NR = 0;
int x1 = 0, f1 = 0, x2, f2;
void citi();
void adauga();
void scrie();
void transforma();
void modifica(char d, int l);
int caut_bin(pair<int, int> A[], int l, int k1, int k2);

void write(pair<int, int> A[])
{
	for(int i = 1 ; i <= NR ; i++)
		printf("%d %d\n", A[i].first, A[i].second);
	printf("\n\n\n");
}

void adauga(int x, int f)
{
	for(int i = f - 2; i <= f + 2 ; i++)
		for(int j = x - 2 ; j <= x + 2 ; j++)
			if(abs(i - f)*abs(i - f) + abs(j - x)*abs(j - x) <= 4 && !(i == 0 && j == 0))
			{
				caplin[++NR].first = i; caplin[NR].second = j;
				capcol[NR].first = j; capcol[NR].second = i;
			}
}

void citi()
{
	cin >> N >> M;
	for(int i = 1 ; i <= N ; i++)
	{
		int x, f;
		cin >> x >> f;
		adauga(x, f);
	}
	transforma();
	for(int i = 1 ; i <= M ; i++)
	{
		char d;
		int l;
		cin >> d >> l;
		modifica(d, l);
	}
}

pair<int, int> ccol[NMAX * 13], clin[NMAX * 13];
void transforma()
{
	sort(caplin + 1, caplin + NR + 1);
	sort(capcol + 1, capcol + NR + 1);
	int nr = 0;
	//write(caplin);
	//write(capcol);
	for(int i = 1 ; i <= NR ; i++)
		if(caplin[i].first != caplin[i - 1].first || caplin[i].second != caplin[i - 1].second)
		{
			clin[++nr].first = caplin[i].first;
			clin[nr].second = caplin[i].second;
		}
	nr = 0;	
	for(int i = 1 ; i <= NR ; i++)
		if(capcol[i].first != capcol[i - 1].first || capcol[i].second != capcol[i - 1].second)
		{
			ccol[++nr].first = capcol[i].first;
			ccol[nr].second = capcol[i].second;
		}
		
	copy(clin + 1, clin + nr + 1, caplin + 1);
	copy(ccol + 1, ccol + nr + 1, capcol + 1);
	NR = nr;
	
	//write(caplin);
	//write(capcol);
}

void modifica(char d, int l)
{
	x2 = x1;
	f2 = f1;
	if(d == 'N')
		f2 +=l;
	else if(d == 'S')
		f2 -= l;
	else if(d == 'E')
		x2 += l;
	else
		x2 -= 1;
	if(x2 != x1)
		REZ += caut_bin(caplin, f2, min(x1 + 1, x2), max(x1 + 1, x2));
	else 
		REZ += caut_bin(capcol, x2, min(f1 + 1, f2), max(f1 + 1, f2));
	x1 = x2;
	f1 = f2;
}

int caut_bin(pair<int, int> A[], int l, int k1, int k2)
{
	//write(A);
	int p1 = 0, p2 = 0;
	int q = 1<<25, val;
	while(q > NR)
		q >>= 1;
	val = q;
	
	for(; q ; q = q>>1)
		if(A[p1 + q].first == l)
		{
			if(A[p1 + q].second < k1)
				p1 += q;
		}
		else if(p1 + q <= NR && A[p1 + q].first < l)
			p1 += q;
			
	for(q = val ; q ; q = q>>1)
		if(A[p2 + q].first == l)
		{
			if(A[p2 + q].second <= k2)
				p2 += q;
		}
		else if(p2 + q <= NR && A[p2 + q].first < l)
			p2 += q;
		
	return p2 - p1;
}

void scrie()
{
	printf("%d\n", REZ);
}

int main()
{
	freopen("zc.in", "r", stdin);
	freopen("zc.out", "w", stdout);
	citi();
	scrie();
	return 0;
}