Pagini recente » Cod sursa (job #1376782) | Cod sursa (job #2046793) | Cod sursa (job #3123215) | Cod sursa (job #141820) | Cod sursa (job #1329260)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int kMaxH = 2000005;
ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
int N, M, W, H, sol, aib[kMaxH];
struct Event {
int tp, x, y;
Event(int tp, int x, int y) {
this->tp = tp;
this->x = x;
this->y = y;
}
bool operator<(const Event &other) const {
if (x == other.x)
return tp < other.tp;
return x < other.x;
}
};
vector<Event> ev;
void AIBUpdate(int pos, int val) {
for (int i = pos; i < kMaxH; i += i & (-i))
aib[i] += val;
}
int AIBQuery(int pos) {
int ans = 0;
for (int i = pos; i > 0; i -= i & (-i))
ans += aib[i];
return ans;
}
int main() {
fin >> N >> M >> W >> H;
while (N--) {
int x, y;
fin >> x >> y;
ev.push_back(Event(0, x, y));
ev.push_back(Event(2, x + W, y));
}
while (M--) {
int x, y;
fin >> x >> y;
ev.push_back(Event(1, x, y));
}
sort(ev.begin(), ev.end());
for (auto it : ev)
if (it.tp == 1) {
sol += AIBQuery(it.y);
} else if (it.tp == 0) {
AIBUpdate(it.y, 1);
AIBUpdate(it.y + H + 1, -1);
} else {
AIBUpdate(it.y, -1);
AIBUpdate(it.y + H + 1, 1);
}
fout << sol << "\n";
return 0;
}