Cod sursa(job #575928)

Utilizator AndreyPAndrei Poenaru AndreyP Data 8 aprilie 2011 22:36:07
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 16010
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int,int >

int n;
pii pun[N];
int v[N];
int *a[64010];
int undeInit=1;
int ret,pr,ul,pr1,ul1;

inline void citire() {
	scanf("%d",&n);

	for(int i=1; i<=n; ++i) {
		scanf("%d%d",&pun[i].fs,&pun[i].sc);
		v[i] = pun[i].fs;
	}
}

void init(int p,int u,int i) {
	if(p>u)
		return;

	if(p==u) {
        	size_t cnt = 0;
		for(int j=undeInit; j<=n && pun[j].fs==pun[undeInit].fs; ++j)
			++cnt;
                a[i] = new int[cnt+1];
		a[i][0] = 0;
		for(int j=undeInit; j<=n && pun[j].fs==pun[undeInit].fs; ++j)
                	a[i][++a[i][0]] = pun[j].sc;
		undeInit += a[i][0];
                return;
	}

	int m = (p+u)>>1;
	init(p,m,(i<<1));
	init(m+1,u,((i<<1)+1));

        a[i] = new int[a[(i<<1)][0]+a[((i<<1)+1)][0]+1];
	a[i][0] = a[(i<<1)][0] + a[((i<<1)+1)][0];
	merge(a[(i<<1)]+1,a[(i<<1)]+a[(i<<1)][0]+1,a[((i<<1)+1)]+1,a[((i<<1)+1)]+a[(i<<1)+1][0]+1,a[i]+1);
}

inline void precalc() {
	sort(pun+1,pun+n+1);
	sort(v+1,v+n+1);
	v[0] = unique(v+1,v+n+1)-(v+1);

	init(1,v[0],1);
}

void query(int p,int u,int i) {
	if(p>u)
		return;

	if(pr<=p && u<ul) {
		ret += upper_bound(a[i]+1,a[i]+a[i][0]+1,ul1)-lower_bound(a[i]+1,a[i]+a[i][0]+1,pr1);
		return;
	}

	if(p==u)
		return;

        int m = (p+u)>>1;

	if(pr<=m)
		query(p,m,(i<<1));
	if(m<ul-1)
		query(m+1,u,((i<<1)+1));
}

inline void rezolva() {
	int m;
	scanf("%d",&m);

	for(int i=0; i<m; ++i) {
		scanf("%d%d%d%d",&pr,&pr1,&ul,&ul1);
		pr = lower_bound(v+1,v+v[0]+1,pr)-v;
                ul = upper_bound(v+1,v+v[0]+1,ul)-v;
		ret = 0;
		query(1,v[0],1);
		printf("%d\n",ret);
	}
}

int main() {
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);

	citire();
	precalc();
	rezolva();

	return 0;
}