Cod sursa(job #2358063)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 27 februarie 2019 21:12:56
Problema Zota & Chidil Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <bits/stdc++.h>

using namespace std;

#define ll long long

unordered_map <int, vector <int> > linie;
unordered_map <int, vector <int> > col;

void baga (int x, int y) {
  if (x == 0 && y == 0)
    return;
  linie[x].push_back (y);
  col[y].push_back (x);
}

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

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

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);
		swap (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 ());
		vector <int> v;
		v.push_back (x.second[0]);
		for (i = 1; i < x.second.size (); i++)
      if (x.second[i] != x.second[i - 1])
        v.push_back (x.second[i]);
    x.second = v;
	}
	for (auto &x : col) {
		sort (x.second.begin (), x.second.end ());
		vector <int> v;
		v.push_back (x.second[0]);
		for (i = 1; i < x.second.size (); i++)
      if (x.second[i] != x.second[i - 1])
        v.push_back (x.second[i]);
    x.second = v;
	}

	sol = 0;
	x = 0; y = 0;
	scanf ("\n");
	//printf ("%d\n", linie[3].size ());
	for (i = 1; i <= m; i++) {
		scanf ("%c %d\n", &c, &val);
		if (c == 'N') {
			xnou = x + val;
			x++;
			sol += findx (x, xnou, y);
			x = xnou;
		}
		if (c == 'S') {
			xnou = x - val;
			x--;
			sol += findx (xnou, x, y);
			x = xnou;
		}
		if (c == 'E') {
			ynou = y + val;
			y++;
			sol += findy (y, ynou, x);
			y = ynou;
		}
		if (c == 'V') {
			ynou = y - val;
			y--;
			sol += findy (ynou, y, x);
			y = ynou;
		}
		//printf ("%lld\n", sol);
		//printf ("%d %d\n", x, y);
	}
	printf ("%lld\n", sol);
	return 0;
}