Pagini recente » Cod sursa (job #3286588) | Cod sursa (job #1699524) | Cod sursa (job #1871937) | Cod sursa (job #700814) | Cod sursa (job #2827766)
#include <bits/stdc++.h>
using namespace std;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
#ifdef INFOARENA
#define cin fin
#define cout fout
InParser fin("ograzi.in");
ofstream fout("ograzi.out");
#endif // INFOARENA
using pii = pair <int, int>;
class FakeBIT2D {
unordered_map <int, unordered_map <int, int>> t;
int n;
int lsb(int x) { return x & (-x); }
public:
FakeBIT2D(int _n) : n(_n), t(n + 1) {}
void fake_query(int x, int y) {
for(; x; x -= lsb(x))
for(int cy = y; cy; cy -= lsb(cy))
t[x][cy] = 0;
}
void add(int x, int y, int val) {
for(; x <= n; x += lsb(x))
for(int cy = y; cy <= n; cy += lsb(cy))
if(t.count(x) && t[x].count(cy))
t[x][cy] += val;
}
int query(int x, int y) {
int res = 0;
for(; x; x -= lsb(x))
for(int cy = y; cy; cy -= lsb(cy))
res += t[x][cy];
return res;
}
};
const int N = 1e6;
vector <pii> queries;
int main()
{
int n, m, w, h, x, y;
cin >> n >> m >> w >> h;
FakeBIT2D B(N + 1); queries.resize(n);
for(int i = 0; i < n; i++) {
cin >> x >> y; x++, y++;
queries[i] = {x, y};
B.fake_query(x + w, y + h);
B.fake_query(x + w, y);
B.fake_query(x, y + h);
B.fake_query(x, y);
}
for(int i = 0; i < m; i++)
cin >> x >> y,
B.add(x, y, 1),
B.add(x + w, y, -1),
B.add(x, y + h, -1),
B.add(x + w, y + h, 1);
int res = 0;
for(int i = 0; i < n; i++)
res += B.query(queries[i].first + w, queries[i].second + h) + B.query(queries[i].first, queries[i].second) -
(B.query(queries[i].first + w, queries[i].second) + B.query(queries[i].first, queries[i].second + h));
cout << res;
return 0;
}