Cod sursa(job #1327975)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 27 ianuarie 2015 18:30:47
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define PII pair <int, int>
using namespace std;
PII a[16001];
int ys[16001][16];
int n,np,yinf,ysup;
void sorty(int li, int ls, int niv)
{   if(ls>=li+1)
    {   for(int i=li;i<=ls;i++) ys[i][niv+1]=ys[i][niv];
        sorty(li,(li+ls)>>1,niv+1);
        sorty(((li+ls)>>1)+1,ls,niv+1);
        int k=li-1, i=li, m=(li+ls)>>1, j=m+1;
        while(i<=m && j<=ls)
            if(ys[i][niv+1]<ys[j][niv+1]) ys[++k][niv]=ys[i++][niv+1];
                else ys[++k][niv]=ys[j++][niv+1];
        while(i<=m) ys[++k][niv]=ys[i++][niv+1];
        while(j<=ls) ys[++k][niv]=ys[j++][niv+1];
    }
}
void search(int ci, int cs, int li, int ls, int niv)
{   int mij,yi1,yi2;
    if(li==ls) {if(ys[li][niv]>=yinf && ys[li][niv]<=ysup) np++;}
    else if(ls>li)
          { if(ci==li && cs==ls)
            {   yi1=ls+1;
                while(li<=ls)
                {   mij=(li+ls)>>1;
                    if(ys[mij][niv]<yinf) li=mij+1; else {yi1=mij; ls=mij-1;}
                }
                li=ci; ls=cs; yi2=li-1;
                while(li<=ls)
                {   mij=(li+ls)>>1;
                    if(ys[mij][niv]>ysup) ls=mij-1; else {yi2=mij; li=mij+1;}
                }
                if(yi1<=yi2) np+=(yi2-yi1+1);
            }
            else
            {   mij=(li+ls)>>1;
                if(ci<=mij)
                    {   if (cs<=mij) search(ci,cs,li,mij,niv+1);
                            else
                            {   search(ci,mij,li,mij,niv+1);
                                search(mij+1,cs,mij+1,ls,niv+1);
                            }
                    }
                else search(ci,cs,mij+1,ls,niv+1);
            }
          }
}
void compute()
{   int nd,li,ls,xa,ya,xb,yb,xi1,xi2,mi;
    freopen("zoo.out","w",stdout);
    scanf("%ld",&nd);
    for(int k=1;k<=nd;k++)
    {   scanf("%ld %ld %ld %ld",&xa,&ya,&xb,&yb);
        if(xa>a[n].x || xb<a[1].x) printf("0\n");
        else
        {   if(xa<a[1].x) xa=1;
            else
            {   li=1; ls=n; xi1=n+1;
                while(li<=ls)
                {   mi=(li+ls)>>1;
                    if(a[mi].x<xa) li=mi+1; else {xi1=mi; ls=mi-1;}
                }
                xa=xi1;
            }
            if (xb>a[n].x) xb=n;
            else
            {   li=1; ls=n; xi2=0;
                while(li<=ls)
                {   mi=(li+ls)>>1;
                    if(a[mi].x>xb) {ls=mi-1;} else {xi2=mi; li=mi+1;}
                }
                xb=xi2;
            }
            if(xa>xb) printf("0\n");
            else
            {   np=0; yinf=ya; ysup=yb;
                search(xa,xb,1,n,0);
                printf("%ld\n",np);
            }
        }
    }
}
int main()
{   freopen("zoo.in","r",stdin);
    scanf("%ld",&n);
    for(int i=1;i<=n;i++) scanf("%ld %ld",&a[i].x,&a[i].y);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) ys[i][0]=a[i].y;
    sorty(1,n,0);
    compute();
    return 0;
}