Pagini recente » Cod sursa (job #582934) | Cod sursa (job #399677) | Cod sursa (job #1558003) | Cod sursa (job #599784) | Cod sursa (job #1074453)
#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;
/*if (poz < 0)
cout << -1 << "\n";
else
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;
/*if (poz < 0)
cout << -1 << "\n\n";
else
cout << P.first << " " << P.second << " " << v[poz].first << " " << v[poz].second << " " << poz << " first\n\n";*/
return poz;
}
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));
y -= dist;
}
if (d == 'N') {
sol += last_query(vx, make_pair(x, y + dist)) - first_query(vx, make_pair (x, y));
y += dist;
}
if (d == 'V') {
sol += last_query(vy, make_pair(y, x)) - first_query(vy, make_pair(y, x - dist));
x -= dist;
}
if (d == 'E') {
sol += last_query(vy, make_pair(y, x + dist)) - first_query(vy, make_pair(y, x));
x +=dist;
}
}
fout << sol;
}