Cod sursa(job #2358113)

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

using namespace std;

#define ll long long

const int MAXN = 523456;
const int INF = 2e9;
vector <int> linie[MAXN + 1], col[MAXN + 1];

int cod (ll val) {
  return (val + INF) % MAXN;
}

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

int cautax (int x, int y) {
	int st, dr, sol;
	st = 0;
	y = cod (y);
	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;
	x = cod (x);
	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 (i = 0; i < MAXN; i++) {
    if (linie[i].size () == 0)
      continue;
		sort (linie[i].begin (), linie[i].end ());
		vector <int> v;
		v.push_back (linie[i][0]);
		for (unsigned j = 1; j < linie[i].size (); j++)
      if (linie[i][j] != linie[i][j - 1])
        v.push_back (linie[i][j]);
    linie[i] = v;
	}
	for (i = 0; i < MAXN; i++) {
    if (col[i].size () == 0)
      continue;
		sort (col[i].begin (), col[i].end ());
		vector <int> v;
		v.push_back (col[i][0]);
		for (unsigned j = 1; j < col[i].size (); j++)
      if (col[i][j] != col[i][j - 1])
        v.push_back (col[i][j]);
    col[i] = 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;
}