Cod sursa(job #196800)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 29 iunie 2008 09:57:35
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<stdio.h>
#define MAX 32001
#define m ((st+dr)>>1)
int n, X[MAX], x1, x2, y1, y2;
int T[15][MAX];
struct Punct{
    int x, y;
} p[MAX];
struct Cmp{
    bool operator () (Punct a, Punct b){
        return (a.x < b.x);
    }
};
int Search(int a[], int l, int r, int v){
    int i,step;
    for(step=1;step<=(r-l)+1;step<<=1);
    for(i=l-1;step;step>>=1)
        if(i+step<=r&&a[i+step]<=v)
            i+=step;
    return i;
}
void Build(int lv,int st,int dr){
    if(st==dr){
        T[lv][st]=p[st].y;
        return;
    }
    Build(lv+1,st,m);
    Build(lv+1,m+1,dr);
    int i,j,k;
    for(i=st,j=m+1,k=st;i<=m||j<=dr;)
        if(j>dr||(i<=m&&T[lv+1][i]<T[lv+1][j]))
            T[lv][k++]=T[lv+1][i++];
        else
            T[lv][k++]=T[lv+1][j++];
}
int Query(int lv,int st,int dr){
    if(x1<=st&&dr<=x2){
        if(y2<T[lv][st]||y1>T[lv][dr])
            return 0;
        if(y1<T[lv][st]&&y2>T[lv][dr])
            return (dr-st)+1;
        return Search(T[lv],st,dr,y2)-Search(T[lv],st,dr,y1-1);
    }
    int t=0;
    if(x1<=m)
		t+=Query(lv+1,st,m);
    if(m<x2)
		t+=Query(lv+1,m+1,dr);
    return t;   
}
int main(){
    int i,q;
	freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    for(i=1;i<=n;i++)
		X[i]=p[i].x;
    Build(1,1,n);
    scanf("%d",&q);
    for(;q>=1;q--){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x2<X[1]||x1>X[n])
			printf("0\n");
		else{
			x1=Search(X,1,n,x1-1)+1;
			x2=Search(X,1,n,x2);
			printf("%d\n",Query(1, 1, n));
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}