Cod sursa(job #828894)

Utilizator deneoAdrian Craciun deneo Data 4 decembrie 2012 16:53:56
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 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 make_point(int x, int y, int type, int poz) {
	point a;
	a.x = x;
	a.y = y;
	a.type = type;
	a.poz = poz;
	return a;
}

int N, M, rez[MAXM], aib[DIMAIB];
vector<point> v;
vector<int> norm;

bool cmp (point a, point b) {
	if (a.x == b.x)
		if (a.type == 0)
			return 1;
		else 0;
	return a.x < b.x;
}

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() {
	fin >> N;

	for (int i = 1; i <= N; ++i) {
		int x, y;
		
		fin >> x >> y;
		v.push_back(make_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 (make_point(x1 - 1, y1 - 1, 1, i));
		v.push_back (make_point(x1 - 1, y2, -1, i));
		v.push_back (make_point(x2, y1 - 1, -1, i));
		v.push_back (make_point(x2, y2, 1, i));
	}

	sort (v.begin(), v.end(), cmp);
	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;
}