Pagini recente » Cod sursa (job #2204807) | Cod sursa (job #2062740) | Cod sursa (job #2004224) | Cod sursa (job #1689066) | Cod sursa (job #1561646)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("ograzi.in");
ofstream out("ograzi.out");
const int MAX_N = 50000;
const int MAX_M = 100000;
const int MAX_H = 1000000;
struct Event {
char type;
int x;
int y;
};
int eCount;
Event E[1 + 4 * MAX_N + MAX_M];
int AIB[1 + MAX_H];
int getLSB(int X) {
return X & (-X);
}
void update(int pos, int val) {
int i;
for(i = pos; i <= MAX_H; i += getLSB(i)) {
AIB[i] += val;
}
}
int query(int pos) {
int i, ans = 0;
for(i = pos; i; i -= getLSB(i)) {
ans += AIB[i];
}
return ans;
}
bool eventSort(Event A, Event B) {
if(A.x == B.x) return A.type < B.type;
return A.x < B.x;
}
int main() {
int n, m, w, h, i, x, y, t, ans = 0;
in >> n >> m >> w >> h;
for(i = 1; i <= n; i++) {
in >> x >> y;
E[++eCount] = Event{0, x, y};
E[++eCount] = Event{1, x, y + h};
E[++eCount] = Event{1, x + w, y};
E[++eCount] = Event{0, x + w, y + h};
}
for(i = 1; i <= m; i++) {
in >> x >> y;
E[++eCount] = Event{2, x, y};
}
sort(E+1, E+eCount+1, eventSort);
for(i = 1; i <= eCount; i++) {
x = E[i].x;
y = E[i].y;
if(E[i].type == 0) {
update(y, 1);
}
else if(E[i].type == 1) {
update(y, -1);
}
else {
ans += query(y);
}
}
out << ans << '\n';
return 0;
}