Cod sursa(job #2022453)

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

using namespace std;

const int N = 16003, inf = -2e9 - 2;
int n, q;
pair<int, int>p[N];
vector<int>aint[4 * N + 2];
void build(int l, int r, int nod) {
	for(int i = l; i <= r; ++i) {
		aint[nod].push_back(p[i].second);
	}
	sort(begin(aint[nod]), end(aint[nod]));
	if(l != r) {
		int m = (l + r) / 2;
		build(l, m, nod * 2);
		build(m + 1, r, nod * 2 + 1);
	}
}
int query(int x1, int y1, int x2, int y2, int l, int r, int nod) {
	if(l > x2 || x1 > r) {
		return 0;
	}
	if(l >= x1 && r <= x2) {
    cerr<<x1<<' '<<x2<<' '<<nod<<endl;
		int p1 = upper_bound(begin(aint[nod]), end(aint[nod]), y1 - 1) - begin(aint[nod]), p2 = upper_bound(begin(aint[nod]), end(aint[nod]), y2) - begin(aint[nod] ) - 1;
		return p2 - p1 + 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 >> p[i].first >> p[i].second;
	sort(p + 1, p + n + 1);
	build(1,n,1);
	cin >> q;
	for(int tc = 1; tc <= q; ++tc) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		pair<int, int> p1 = {x1, inf};
		int pos1 = upper_bound(p + 1, p + n + 1, p1) - p;
		p1 = {x2, inf};
		int pos2 = upper_bound(p + 1, p + n + 1, p1) - p;
		cout << query(pos1, y1, pos2, y2, 1, n, 1) << '\n';
	}
}