Cod sursa(job #358754)

Utilizator ProtomanAndrei Purice Protoman Data 24 octombrie 2009 13:31:17
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <algorithm>
#include <stdio.h>
#include <map>
#include <vector>

#define MAX 1500000
#define mp make_pair
#define pb push_back
#define x first
#define y second

using namespace std;

map <char, int> mapDir;
map <pair <int, int>, bool> sel;
pair <int, int> vctX[MAX], vctY[MAX];
int dirX[] = {0, 0, 1, -1};
int dirY[] = {1, -1, 0, 0};
int bomb, pasi, nrPasi, nrAf, sol;

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

	sel[mp(x, y)] = 1;
	vctX[++nrAf] = mp(x, y);
	vctY[nrAf] = mp(y, x);
}

inline int cautaBinX(int fr, int ls, int c1, int c2)
{
	int med = (fr + ls) / 2;

	if ((vctX[med].x < c1 || (vctX[med].x == c1 && vctX[med].y <= c2)) && (vctX[med + 1].x > c1 || (vctX[med + 1].x  == c1 && vctX[med + 1].y > c2)))
		return med;

	if (vctX[med].x > c1 || (vctX[med].x == c1 && vctX[med].y > c2))
		cautaBinX(fr, med - 1, c1, c2);
	else cautaBinX(med + 1, ls, c1, c2);
}

inline int cautaBinY(int fr, int ls, int c1, int c2)
{
	int med = (fr + ls) / 2;

	if ((vctY[med].x < c1 || (vctY[med].x == c1 && vctY[med].y <= c2)) && (vctY[med + 1].x > c1 || (vctY[med + 1].x  == c1 && vctY[med + 1].y > c2)))
		return med;

	if (vctY[med].x > c1 || (vctY[med].x == c1 && vctY[med].y > c2))
		cautaBinY(fr, med - 1, c1, c2);
	else cautaBinY(med + 1, ls, c1, c2);
}

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

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

	sel[mp(0, 0)] = 1;
	vctX[0] = vctY[0] = mp(-LONG_MAX, -LONG_MAX);
	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(vctX + 1, vctX + 1 + nrAf);
	sort(vctY + 1, vctY + 1 + nrAf);

	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 + dirX[dir] * nrPasi;
		int y1 = y + dirY[dir] * nrPasi;

		if (dir == 0)
			sol += cautaBinX(0, nrAf, x1, y1) - cautaBinX(0, nrAf, x, y);
		if (dir == 1)
			sol += (nrAf - cautaBinX(0, nrAf, x1, y1)) - (nrAf - cautaBinX(0, nrAf, x, y));
		if (dir == 2)
			sol += cautaBinY(0, nrAf, y1, x1) - cautaBinY(0, nrAf, y, x);
		if (dir == 3)
			sol += (nrAf - cautaBinY(0, nrAf, y1, x1)) - (nrAf - cautaBinY(0, nrAf, y, x));

		x = x1;
		y = y1;
	}

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

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