Cod sursa(job #1329260)

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