Pagini recente » Cod sursa (job #1960470) | Cod sursa (job #2515349) | Cod sursa (job #2219154) | Cod sursa (job #1813592) | Cod sursa (job #3187012)
#include <bits/stdc++.h>
using namespace std;
const int V_MAX = 1000005;
struct BIT {
int bit[4 * V_MAX + 5];
static inline int lsb(int x) {
return (x ^ (x - 1)) & x;
}
int query(int pos) {
int ret = 0;
for(; pos >= 1; pos -= lsb(pos)) {
ret += bit[pos];
}
return ret;
}
void update(int pos, int val) {
for(; pos <= V_MAX; pos += lsb(pos)) {
bit[pos] += val;
}
}
};
struct Point {
int x, y;
int t;
bool operator<(const Point &oth) const {
return x < oth.x || (x == oth.x && y < oth.y);
}
};
int N, M, H, W;
Point P[V_MAX + 5];
vector <Point> E;
BIT T;
int main() {
#ifndef LOCAL
freopen("ograzi.in", "r", stdin);
freopen("ograzi.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> W >> H;
for(int i = 1; i <= N; i++) {
int x, y;
cin >> x >> y;
y++;
E.push_back({x, y, 1});
E.push_back({x + W + 1, y, -1});
}
for(int i = 1; i <= M; i++) {
cin >> P[i].x >> P[i].y;
P[i].y++;
}
sort(E.begin(), E.end());
sort(P + 1, P + M + 1);
int j = 0;
int ans = 0;
for(int i = 1; i <= M; i++) {
while(j < (int)E.size() && E[j].x <= P[i].x) {
T.update(E[j].y, E[j].t);
j++;
}
ans += T.query(P[i].y) - T.query(P[i].y - H - 1);
}
cout << ans << "\n";
return 0;
}