Cod sursa(job #1329266)

Utilizator vladrochianVlad Rochian vladrochian Data 29 ianuarie 2015 12:18:56
Problema Ograzi Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#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;
}