Cod sursa(job #2589919)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 27 martie 2020 10:33:18
Problema Zota & Chidil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
 
vector <pair <int, int> > linie, col;
const int SIZE = 1 << 10;
int pointer = SIZE;
char buffer[SIZE];
 
inline char advance() {
  if (pointer == SIZE) {
    fread(buffer, 1, SIZE, stdin);
    pointer = 0;
  }
  return buffer[pointer++];
}
 
inline int read() {
  int answer = 0, sign = 1;
  char ch = advance();
  while (!isdigit(ch) && ch != '-')
      ch = advance();
  if (ch == '-') {
      sign *= -1;
      ch = advance();
  }
  while (isdigit(ch)) {
      answer = answer * 10 + ch - '0';
      ch = advance();
  }
  return answer * sign;
}
inline void baga (int x, int y) {
  if (x == 0 && y == 0)
    return;
  linie.push_back ({x, y});
}
 
inline int cautax (int x, int y) {
	int st, dr, sol;
	st = 0;
	dr = col.size () - 1;
	sol = -1;
	pair <int, int> goal = {y, x};
	while (st <= dr) {
		int mij = (st + dr) / 2;
		if (col[mij].first < goal.first || (col[mij].first == goal.first && col[mij].second <= goal.second)) {
			st = mij + 1;
			sol = mij;
		}
		else
			dr = mij - 1;
	}
	return sol + 1;
}
 
inline int cautay (int y, int x) {
	int st, dr, sol;
	st = 0;
	dr = linie.size () - 1;
	sol = -1;
 
	pair <int, int> goal = {x, y};
	while (st <= dr) {
		int mij = (st + dr) / 2;
		if (linie[mij].first < goal.first || (linie[mij].first == goal.first && linie[mij].second <= goal.second)) {
			st = mij + 1;
			sol = mij;
		}
		else
			dr = mij - 1;
	}
	return sol + 1;
}
 
inline int findx (int x1, int x2, int y) {
	return cautax (x2, y) - cautax (x1 - 1, y);
}
 
inline 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);
	n = read (); m = read ();
	for (i = 1; i <= n; i++) {
		x = read (); y = read ();
		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);
	}
    sort (linie.begin (), linie.end ());
    vector <pair <int, int> > v;
    v.push_back (linie[0]);
    for (unsigned j = 1; j < linie.size (); j++)
      if (linie[j] != linie[j - 1])
        v.push_back (linie[j]);
    linie = v;
    for (auto x : linie)
        col.push_back ({x.second, x.first});
    sort (col.begin (), col.end ());
	sol = 0;
	x = 0; y = 0;
	for (i = 1; i <= m; i++) {
        c = advance (); val = read ();
		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);
	return 0;
}