Cod sursa(job #2357244)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 27 februarie 2019 11:05:18
Problema Zota & Chidil Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;
unordered_map <int, vector <int> > linie;
unordered_map <pair<int, int>, int> exists;
unordered_map <int, vector <int> > col;
void baga (int x, int y) {
	if (exists[{x, y}] == 0) {
		linie[x].push_back (y);
		col[y].push_back (x);
		exists[{x, y}] = 1;
	}
}
#define ll long long

int cautax (int x, int y) {
	int st, dr, sol;
	st = 0;
	dr = col[y].size () - 1;
	sol = 0;
	while (st <= dr) {
		int mij = (st + dr) / 2;
		if (col[y][mij] <= x) {
			st = mij + 1;
			sol = mij;
		}
		else
			dr = mij - 1;
	}
	return sol;
}
int cautay (int y, int x) {
	int st, dr, sol;
	st = 0;
	dr = linie[x].size () - 1;
	sol = 0;
	while (st <= dr) {
		int mij = (st + dr) / 2;
		if (linie[x][mij] <= y) {
			st = mij + 1;
			sol = mij;
		}
		else
			dr = mij - 1;
	}
	return sol;
}

int findx (int x1, int x2, int y) {
	return cautax (x2, y) - cautax (x1 - 1, y);
}
int findy (int y1, int y2, int x) {
	return cautay (y2, x) - cautay (y1 - 1, x);
}
int main() {
	freopen ("zc.in", "r", stdin);
	freopen ("zc.out", "w", stdout);
	scanf ("%d%d", &n, &m);
	for (i = 1; i <= n; i++) {
		scanf ("%d%d", &x, &y);
		baga (x - 2, y);
		baga (x - 1, y - 1);
		baga (x - 1, y);
		baga (x - 1, y + 1);
		baga (x, y - 2);
		baga (x, y - 1);
		baga (x, y);
		baga (x, y + 1);
		baga (x, y + 2);
		baga (x + 1, y - 1);
		baga (x + 1, y);
		baga (x + 1, y + 1);
		baga (x + 2, y);
	}
	for (auto &x : linie) {
		sort (x.second.begin (), x.second.end ());
	}
	for (auto &x : col) {
		sort (x.second.begin (), x.second.end ());
	}
	sol = 0;
	x = 0; y = 0;
	scanf ("\n");
	for (i = 1; i <= m; i++) {
		scanf ("%c %d\n", &c, &val);
		if (c == 'N') {
			xnou = x + val;
			x++;
			sol += findx (x, xnou, y);
		}
		if (c == 'S') {
			xnou = x - val;
			x--;
			sol += findx (xnou, x, y);
		}
		if (c == 'E') {
			ynou = y + val;
			y++;
			sol += findy (y, ynou, x);
		}
		if (c == 'V') {
			ynou = y - val;
			y--;
			sol += findy (ynou, y, x);
		}
	}
	printf ("%lld\n", sol);
	return 0;
}