Cod sursa(job #828901)

Utilizator deneoAdrian Craciun deneo Data 4 decembrie 2012 17:16:07
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

#define MAXM 110000
#define DIMAIB 510000

ifstream fin ("zoo.in");
ofstream fout("zoo.out");

struct point {
	int x, y, type, poz;
	point(int xx, int yy, int t, int p) {
		x = xx;
		y = yy;
		type = t;
		poz = p;
	}
	bool operator < (const point &other) const {
		if (x == other.x) {
			if (type == 0) {
				return true;
			} else {
				return false;
			}
		}
		return x < other.x;
	}
};

int N, M, rez[MAXM], aib[DIMAIB];

inline void insert_aib(int poz, int elem) {
	while (poz <= DIMAIB) {
		aib[poz] += elem;
		poz += poz & (-poz);
	}
}

inline int query(int poz) {
	int sum = 0;
	
	while (poz > 0) {
		sum += aib[poz];
		poz -= poz & (-poz);
	}
	
	return sum;
}

int main() {
	
	vector<point> v;
	vector<int> norm;
	
	fin >> N;
	
	v.reserve(DIMAIB);
	norm.reserve(DIMAIB);
	
	for (int i = 1; i <= N; ++i) {
		int x, y;
		
		fin >> x >> y;
		
		norm.push_back(y);
		v.push_back(point(x, y, 0, 0));

	}
	fin >> M;
	for (int i = 1; i <= M; ++i) {
		int x1, y1, x2, y2;
		fin >> x1 >> y1 >> x2 >> y2;
		
		norm.push_back(y1);
		norm.push_back(y2);
		norm.push_back(y1 - 1);
		norm.push_back(y2 - 1);
		
		v.push_back (point(x1 - 1, y1 - 1, 1, i));
		v.push_back (point(x1 - 1, y2, -1, i));
		v.push_back (point(x2, y1 - 1, -1, i));
		v.push_back (point(x2, y2, 1, i));
	}

	sort (v.begin(), v.end());
	sort (norm.begin(), norm.end());

	norm.resize(unique(norm.begin(), norm.end()) - norm.begin());
	
	for (int i = 0; i < v.size(); ++i) 
		v[i].y = lower_bound(norm.begin(), norm.end(), v[i].y) - norm.begin() + 1;

	for (int i = 0; i < v.size(); ++i) {
		//cerr << "query " << v[i].x << " " << v[i].y << " " << v[i].type << " " << v[i].poz << "\n";
		switch(v[i].type) {
			case 0: {
				insert_aib(v[i].y, 1);
				break;
				}
			case -1: {
				rez[v[i].poz] -= query (v[i].y);
				break;
			}
			case 1: {
				rez[v[i].poz] += query (v[i].y);
				break;
			}
		}
	}
	for (int i = 1; i <= M; ++i)
		fout << rez[i] << "\n";
	return 0;
}