Cod sursa(job #1490367)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 23 septembrie 2015 12:48:16
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

class orthogonal_range_search{
	const int n;
	vector<vector<int> > points;
	vector<int> xs;
public:
	explicit orthogonal_range_search(vector<pair<int, int> >& pts):
		n(pts.size()), points(2*n){
		sort(begin(pts), end(pts), [](const pair<int, int> a, const pair<int, int> b){
			return a.first < b.first; });
		for(int i = 0; i < pts.size(); ++i){
			xs.push_back(pts[i].first);
			points[i+n].push_back(pts[i].second); }
		for(int i = n-1; i > 0; --i){
			points[i].resize(points[2*i].size() +
				points[2*i+1].size());

			merge(begin(points[2*i]), end(points[2*i]),
				begin(points[2*i+1]), end(points[2*i+1]),
				begin(points[i])); } }
	int query(const int x1, const int y1, const int x2, const int y2){
		int rez = 0;
		for(int st = lower_bound(begin(xs), end(xs), x1)-begin(xs)+n,
			dr = upper_bound(begin(xs), end(xs), x2)-begin(xs)+n;
			st < dr;
			st /= 2, dr /= 2){
			if(st%2 == 1){
				rez += upper_bound(begin(points[st]), end(points[st]), y2) -
					lower_bound(begin(points[st]), end(points[st]), y1);
				++st; }
			if(dr%2 == 1){
				--dr;
				rez += upper_bound(begin(points[dr]), end(points[dr]), y2) -
					lower_bound(begin(points[dr]), end(points[dr]), y1); } }
		return rez; } };

int main(){
	ifstream f("zoo.in");
	ofstream g("zoo.out");
	int n;
	f >> n;
	vector<pair<int, int> > v(n);
	for(auto& x : v){
		f >> x.first >> x.second; }
	orthogonal_range_search ors(v);
	int m;
	f >> m;
	for(int i = 0, x1, y1, x2, y2; i < m; ++i){
		f >> x1 >> y1 >> x2 >> y2;
		g << ors.query(x1, y1, x2, y2) << '\n'; }
	return 0; }