Pagini recente » Cod sursa (job #2679219) | Cod sursa (job #488234) | Cod sursa (job #1240323) | Cod sursa (job #1812099) | Cod sursa (job #1329266)
#include <fstream>
#include <algorithm>
using namespace std;
const int kMaxE = 200005, kMaxH = 2000005;
ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
int N, M, W, H, sol, aib[kMaxH], es;
struct Event {
int tp, x, y;
bool operator<(const Event &other) const {
if (x == other.x)
return tp < other.tp;
return x < other.x;
}
} ev[kMaxE];
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[es].tp = 0;
ev[es].x = x;
ev[es].y = y;
++es;
ev[es].tp = 2;
ev[es].x = x + W;
ev[es].y = y;
++es;
}
while (M--) {
int x, y;
fin >> x >> y;
ev[es].tp = 1;
ev[es].x = x;
ev[es].y = y;
++es;
}
sort(ev, ev + es);
for (int i = 0; i < es; ++i)
if (ev[i].tp == 1) {
sol += AIBQuery(ev[i].y);
} else if (ev[i].tp == 0) {
AIBUpdate(ev[i].y, 1);
AIBUpdate(ev[i].y + H + 1, -1);
} else {
AIBUpdate(ev[i].y, -1);
AIBUpdate(ev[i].y + H + 1, 1);
}
fout << sol << "\n";
return 0;
}