Cod sursa(job #1329271)

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