Cod sursa(job #2357937)

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

using namespace std;

#define ll long long

unordered_map <int, vector <int> > linie;
unordered_map <long double, int> exists;
unordered_map <int, vector <int> > col;
long double cod (int x, int y) {
  return 1.0 * (x + 2e9) * (1.0 * 4e9 + 1) + y + 2e9;
}
void baga (int x, int y) {
	if (exists[cod (x, y)] == 0) {
		linie[x].push_back (y);
		col[y].push_back (x);
		exists[cod (x, y)] = 1;
	}
}
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() {
  int n, m, i, x, y, val, xnou, ynou;
  ll sol;
  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", &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 ());
		/*printf ("%d: ", x.first);
		for (auto y : x.second)
      printf ("%d ", y);
    printf ("\n");*/
	}

	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;
      if (i == 1)
        xnou++;
			x++;
			sol += findx (x, xnou, y);
			x = xnou;
		}
		if (c == 'S') {
			xnou = x - val;
			if (i == 1)
        xnou--;
			x--;
			sol += findx (xnou, x, y);
			x = xnou;
		}
		if (c == 'E') {
			ynou = y + val;
			if (i == 1)
        ynou++;
			y++;
			sol += findy (y, ynou, x);
			y = ynou;
		}
		if (c == 'V') {
			ynou = y - val;
			if (i == 1)
        ynou--;
			y--;
			sol += findy (ynou, y, x);
			y = ynou;
		}
		//printf ("%d %d\n", x, y);
	}
	printf ("%lld\n", sol);
	return 0;
}