Cod sursa(job #345078)

Utilizator ProtomanAndrei Purice Protoman Data 1 septembrie 2009 17:11:50
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <algorithm>
#include <stdio.h>
#include <set>
#include <map>
#include <vector>

#define ll long long
#define mp make_pair
#define pb push_back
#define f first
#define s second

using namespace std;

map <char, int> mapDir;
map <pair <int, int>, bool> sel;
vector <pair <int, int> > vctAf;
int dirX[] = {0, 0, 1, -1};
int dirY[] = {1, -1, 0, 0};
int bomb, pasi, nrPasi;
ll sol;
set <pair <pair <int, int>, int> > setX, setY;

inline void baga(int x, int y)
{
	if (sel[mp(x, y)])
		return;

	sel[mp(x, y)] = 1;
	vctAf.pb(mp(x, y));
}

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

	scanf("%d %d\n", &bomb, &pasi);

	sel[mp(0, 0)] = 1;
	for (int i = 1; i <= bomb; i++)
	{
		int x, y;
		scanf("%d %d\n", &x, &y);

		for (int i = x - 2; i <= x + 2; i++)
			for (int j = y - (2 - abs(x - i)); j <= y + (2 - abs(x - i)); j++)
				baga(i, j);
	}
	baga(LONG_MAX, LONG_MAX);

	sort(vctAf.begin(), vctAf.end());
	for (int i = 0; i < vctAf.size(); i++)
	{
		setX.insert(mp(vctAf[i], i));

		swap(vctAf[i].f, vctAf[i].s);
	}

	sort(vctAf.begin(), vctAf.end());
	for (int i = 0; i < vctAf.size(); i++)
		setY.insert(mp(vctAf[i], i));

	mapDir['N'] = 0;
	mapDir['S'] = 1;
	mapDir['E'] = 2;
	mapDir['V'] = 3;

	int x = 0, y = 0;
	for (int i = 1; i <= pasi; i++)
	{
		char pc;
		scanf("%c %d\n", &pc, &nrPasi);

		int dir = mapDir[pc];
		int x1 = x + nrPasi * dirX[dir];
		int y1 = y + nrPasi * dirY[dir];

		if (dir < 2)
			sol += (ll) (*setX.lower_bound(mp(mp(x1, y1), 0))).s - (*setX.upper_bound(mp(mp(x, y), 0))).s;
		else
			sol += (ll) (*setY.lower_bound(mp(mp(y1, x1), 0))).s - (*setY.upper_bound(mp(mp(y, x), 0))).s;

		x = x1;
		y = y1;
	}

	printf("%lld\n", sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}