Pagini recente » Cod sursa (job #821600) | Cod sursa (job #458814) | Cod sursa (job #1806900) | Cod sursa (job #424968) | Cod sursa (job #1329271)
#include <fstream>
#include <algorithm>
using namespace std;
const int kMaxE = 200005, kMaxH = 2000005;
ifstream fin("ograzi.in");
ofstream fout("ograzi.out");
char buffer[40], *p;
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 Parse(int &x) {
x = 0;
while (*p < '0')
++p;
while (*p >= '0')
x = x * 10 + *(p++) - '0';
}
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.getline(buffer, 40);
p = buffer;
Parse(N);
Parse(M);
Parse(W);
Parse(H);
while (N--) {
int x, y;
fin.getline(buffer, 40);
p = buffer;
Parse(x);
Parse(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.getline(buffer, 40);
p = buffer;
Parse(x);
Parse(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;
}