Pagini recente » Cod sursa (job #2271684) | Monitorul de evaluare | Cod sursa (job #407795) | Cod sursa (job #1617751) | Cod sursa (job #1074443)
#include <fstream>
#include <algorithm>
//#include <iostream>
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
const int N = 14e5 + 5;
pair <int, int> vx[N], vy[N];
int n, m, x, y, k, kx;
long long sol;
int abs(int x) {
return (x > -x ? x : -x);
}
int last_query(pair<int, int> v[N], pair <int, int> P) {
int poz = -1;
for (int step = (1 << 17); step; step >>=1)
if (poz + step < k && v[poz + step] <= P)
poz += step;
//cout << P.first << " " << P.second << " " << v[poz].first << " " << v[poz].second << " " << poz << " last\n";
return poz;
}
int first_query(pair <int, int> v[N], pair <int, int> P) {
int poz = -1;
for (int step = (1 << 17); step; step >>= 1)
if (poz + step < k && v[poz + step] < P)
poz += step;
//cout << P.first << " " << P.second << " " << v[poz+1].first << " " << v[poz+1].second << " " << poz+1 << " first\n\n";
return poz + 1;
}
int main() {
fin >> n >> m;
while (n--) {
int x, y;
fin >> x >> y;
for (int i = -2; i <= 2; ++i)
for (int j = -2; j <= 2; ++j)
if (abs(i) + abs(j) <= 2 && (x+i || y+j))
vx[kx++] = make_pair (x+i, y+j);
}
sort (vx, vx + kx);
for (int i = 0; i < kx; ++i)
if (!i || vx[i] != vx[i-1])
vx[k++] = vx[i];
for (int i = 0; i < k; ++i)
vy[i] = make_pair (vx[i].second, vx[i].first);
sort (vy, vy + k);
// for (int i = 0; i < k; ++i)
// cout << vx[i].first << " " << vx[i].second << "\n";
//cout << "======\n";
// for (int i = 0; i < k; ++i)
// cout << vy[i].second << " " << vy[i].first << "\n";
// cout << "\n";
while (m--) {
char d; int dist;
fin >> d >> dist;
if (d == 'S') {
sol += last_query(vx, make_pair(x, y)) - first_query(vx, make_pair (x, y - dist)) + 1;
y -= dist;
}
if (d == 'N') {
sol += last_query(vx, make_pair(x, y + dist)) - first_query(vx, make_pair (x, y)) + 1;
y += dist;
}
if (d == 'V') {
sol += last_query(vy, make_pair(y, x)) - first_query(vy, make_pair(y, x - dist)) + 1;
x -= dist;
}
if (d == 'E') {
sol += last_query(vy, make_pair(y, x + dist)) - first_query(vy, make_pair(y, x)) + 1;
x +=dist;
}
}
fout << sol;
}