Cod sursa(job #2022449)

Utilizator lflorin29Florin Laiu lflorin29 Data 16 septembrie 2017 16:15:09
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 16000 * 2 + 5;

int n, q, x[N], y[N];
vector<int>coords;
vector<int>aint[8 * N + 2];
void uniq(vector<int>&th) {
	sort(begin(th), end(th));
	th.resize(unique(begin(th), end(th)) - begin(th));
}
void add(int cx, int cy, int l, int r, int nod) {
	aint[nod].push_back(cy);
	if(l == r) return;
	int m = (l + r) / 2;
	if(cx <= m) {
		add(cx, cy, l, m, nod * 2);
	} else add(cx, cy, m + 1, r, nod * 2 + 1);
}
int query(int x1, int y1, int x2, int y2, int l, int r, int nod) {
	if(x1 > r || l > x2) {
		return 0;
	}
	if(l >= x1 && r <= x2) {
		int pos1 = upper_bound(begin(aint[nod]), end(aint[nod]), y1 - 1) - begin(aint[nod]) ;
		int pos2 = upper_bound(begin(aint[nod]), end(aint[nod]), y2) - begin(aint[nod]) - 1;
		assert(pos2 - pos1 + 1 >= 0);
		return pos2 - pos1 + 1;
	}
	int m = (l + r) / 2;
	return query(x1, y1, x2, y2, l, m, nod * 2) + query(x1, y1, x2, y2, m + 1, r, nod * 2 + 1);
}
int main() {
	ifstream cin("zoo.in");
	ofstream cout("zoo.out");
	cin >> n;
	for(int i = 1; i <= n; ++i)cin >> x[i] >> y[i], coords.push_back(x[i]), coords.push_back(y[i]);
	uniq (coords);
	cin >> q;
	for(int i = 1; i <= n; ++i) {
		x[i] = lower_bound(begin(coords), end(coords), x[i]) - begin(coords) + 1;
		y[i] = lower_bound(begin(coords), end(coords), y[i]) - begin(coords) + 1;
		add(x[i], y[i], 1, coords.size(), 1);
	}
	for(int i = 1; i <= 4 * coords.size(); ++i)
		sort(aint[i].begin(), aint[i].end());
	for(int i = 0; i < q; ++i) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1 = upper_bound(begin(coords), end(coords), x1) - begin(coords) - 1;
		x2 = upper_bound(begin(coords), end(coords), x2) - begin(coords) - 1;
		y1 = upper_bound(begin(coords), end(coords), y1) - begin(coords) - 1;
		y2 = upper_bound(begin(coords), end(coords), y2) - begin(coords) - 1;
		++x1, ++x2, ++y1, ++y2;
		//cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		cout << query(x1, y1, x2, y2, 1, coords.size(), 1) << '\n';
	}
}