Cod sursa(job #2020390)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 10 septembrie 2017 00:42:57
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
#define NMAX 16005
#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

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

pair<int,int> v[NMAX];
vector<int> aib[4*NMAX];
int x1,x2,Y1,Y2;

void build_aib(int nod, int st, int dr) {
	for(int i=st;i<=dr;++i) aib[nod].push_back(v[i].y);
	sort(aib[nod].begin(),aib[nod].end());

	if(st==dr) return;

	int fs=(nod<<1),mid=(st+dr)/2;

	build_aib(fs,st,mid);
	build_aib(fs+1,mid+1,dr);
}

int query_aib(int nod, int st, int dr, int qst, int qdr) {
	int fs=(nod<<1),mid=(st+dr)/2,ans=0;

	if(st>=qst && dr<=qdr)
		return upper_bound(aib[nod].begin(),aib[nod].end(),Y2) - lower_bound(aib[nod].begin(),aib[nod].end(),Y1);

	if(mid>=qst)
		ans+=query_aib(fs,st,mid,qst,qdr);
	if(mid<qdr)
		ans+=query_aib(fs+1,mid+1,dr,qst,qdr);

	return ans;
}

int main() {
	int n,i,m,st,dr;

	fin>>n;
	for(i=1;i<=n;++i)
		fin>>v[i].x>>v[i].y;

	sort(v+1,v+n+1);

	build_aib(1,1,n);

	fin>>m;
	for(i=1;i<=m;++i) {
		fin>>x1>>Y1>>x2>>Y2;

		st=lower_bound(v+1,v+n+1,make_pair(x1,Y1))-v;
		dr=upper_bound(v+1,v+n+1,make_pair(x2,Y2))-v-1;

		if(st>dr) fout<<"0\n";
		else fout<<query_aib(1,1,n,st,dr)<<'\n';
	}

	return 0;
}