Cod sursa(job #477789)

Utilizator freak93Adrian Budau freak93 Data 16 august 2010 13:01:49
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second

using namespace std;

const char iname[]="zoo.in";
const char oname[]="zoo.out";
const int maxn=17000;
const int logn=22;
const int inf=(1<<31)-1;

ifstream f(iname);
ofstream g(oname);

int arb[logn][maxn],i,j,n,q,x1,y1,x2,y2;

pair<int,int> a[maxn];

void build(int level,int left,int right)
{
    if(left==right)
    {
        arb[level][left]=a[left].y;
        return;
    }
    int mid=(left+right)>>1;
    build(level+1,left,mid);
    build(level+1,mid+1,right);
    int j=left,p=mid+1;
    for(int i=left;i<=right;++i)
        if(j>mid)
            arb[level][i]=arb[level+1][p],++p;
        else
            if(p>right)
                arb[level][i]=arb[level+1][j],++j;
            else
                if(arb[level+1][j]<arb[level+1][p])
                    arb[level][i]=arb[level+1][j],++j;
                else
                    arb[level][i]=arb[level+1][p],++p;
}

template<class T>
int bs(T* sir,T elem, int n)
{
    int i,step;
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=n&&sir[i+step]<=elem)
            i+=step;
    return i;
}

int query(int level,int left,int right,int start,int finish,int v1,int v2)
{
    if(start<=left&&right<=finish)
        return bs(arb[level]+left-1,v2,right-left+1)-bs(arb[level]+left-1,v1,right-left+1);
    int mid=(left+right)>>1;
    int rez=0;
    if(start<=mid)
        rez+=query(level+1,left,mid,start,finish,v1,v2);
    if(mid<finish)
        rez+=query(level+1,mid+1,right,start,finish,v1,v2);
    return rez;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    build(1,1,n);
    f>>q;
    for(i=1;i<=q;++i)
    {
        f>>x1>>y1>>x2>>y2;
        g<<query(1,1,n,bs(a,make_pair(x1-1,inf),n)+1,bs(a,make_pair(x2,inf),n),y1-1,y2)<<"\n";
    }
}