Cod sursa(job #500900)

Utilizator cont_de_testeCont Teste cont_de_teste Data 13 noiembrie 2010 15:52:50
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cassert>

using namespace std;

#define pii 	pair<int,int>
#define ff 		first
#define ss 		second
#define maxN 	100100
#define maxM 	2000000
#define all(v) 	v.begin(), v.end()

pii A[maxN], now, next;
vector < pii > X, Y;
int N, M, Nxy, Sol;

void baga_marfa (int x) {
	int i, j;
	for (i = -2; i <= 2; ++ i)
		for (j = -2; j <= 2; ++ j)
			if (abs(i) + abs(j) <= 2 && (A[x].ff + i || A[x].ss + j )) {
				X.push_back(make_pair(A[x].ff + i, A[x].ss + j));
				Y.push_back(make_pair(A[x].ss + j, A[x].ff + i));
			}
}

void do_it (int c, int val) {
	next = now;
	vector < pii > :: iterator it1, it2;
	pii tmp;

	if (c == 'N') {
		next.ss += val;
		it1 = upper_bound(all(X), now);
		it2 = upper_bound(all(X), next);
		Sol += abs(it2 - it1);
	}
	else if (c == 'S') {
		next.ss -= val;
		tmp = now;
		it1 = lower_bound(all(X), next);
		it2 = lower_bound(all(X), tmp);
		Sol += abs(it2 - it1);
	}
	else if (c == 'V') {
		next.ff -= val;
		tmp.ff = next.ss; tmp.ss = next.ff;
		it1 = lower_bound(all(Y), tmp);
		tmp.ff = now.ss; tmp.ss = now.ff;
		it2 = lower_bound(all(Y), tmp);
		Sol += abs(it2 - it1);
	}
	else {
		next.ff += val;
		tmp.ff = now.ss; tmp.ss = now.ff;
		it1 = upper_bound(all(Y), tmp);
		tmp.ff = next.ss; tmp.ss = next.ff;
		it2 = upper_bound(all(Y), tmp);
		Sol += abs(it2 - it1);
	}
	now = next;
}
int main () {
	int i, val;
	vector < pii > :: iterator it;
	char c;

	freopen("zc.in", "r", stdin);
	freopen("zc.out", "w", stdout);

	scanf("%d%d", &N, &M);

	for (i = 1; i <= N; ++ i) {
		scanf("%d%d", &A[i].ff, &A[i].ss);
		baga_marfa (i);
	}

	sort (X.begin(), X.end());
	X.resize(unique(X.begin(), X.end()) - X.begin());

	sort (Y.begin(), Y.end());
	Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

	for (; M -- ;) {
		scanf(" %c %d", &c, &val);
		assert(c == 'V' || c == 'E' || c == 'N' || c == 'S');
		do_it (c, val);
	}

	printf("%d\n", Sol);
}