Cod sursa(job #1153157)

Utilizator Kira96Denis Mita Kira96 Data 25 martie 2014 11:54:00
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include<fstream>
#define fi first
#include<algorithm>
#define se second
#include<vector>
#define N 65000
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
vector<int> H[N];
pair<int,int> v[N];
int sol,i,n,xj,m,yj,xs,ys;
int cbd(int po,int x)
{
    int st=0,sol=-1,dr=H[po].size()-1;
    while(st<=dr)
    {
        int mij=(st+dr)>>1;
        if(x>=H[po][mij])
        {
            sol=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    return sol;
}
int cbs(int po,int x)
{
    int st=0,sol=H[po].size(),dr=H[po].size()-1;
    while(st<=dr)
    {
        int mij=(st+dr)>>1;
        if(x<=H[po][mij])
        {
            sol=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    return sol;
}
void build(int st,int dr,int po)
{
    if(st==dr)
    {
        H[po].push_back(0);
        return;
    }
    int mij=(st+dr)>>1;
    if(i<=mij)
    build(st,mij,po<<1);
    else
    build(mij+1,dr,(po<<1)+1);
    H[po].push_back(0);
}
void upd(int st,int dr,int po)
{
    if(st==dr)
    {
        H[po][0]=v[i].se;
        return ;
    }
    int mij=(st+dr)>>1;
    if(i<=mij)
    upd(st,mij,po<<1);
    else
    upd(mij+1,dr,(po<<1)+1);
    if(i==dr)
    {
    int i=0,j=0,t=-1;
    for(;i<H[po<<1].size()&&j<H[(po<<1)+1].size();)
    {
        if(H[po<<1][i]<H[(po<<1)+1][j])
            H[po][++t]=H[po<<1][i++];
        else
            H[po][++t]=H[(po<<1)+1][j++];
    }
    for(;i<H[po<<1].size();)
        H[po][++t]=H[po<<1][i++];
    for(;j<H[(po<<1)+1].size();)
        H[po][++t]=H[(po<<1)+1][j++];
    }
}
void query(int st,int dr,int po)
{
    if(xj<=v[st].fi&&xs>=v[dr].fi)
    {
        vector<int>::iterator lo=lower_bound(H[po].begin(),H[po].end(),yj);
        vector<int>::iterator hi=upper_bound(H[po].begin(),H[po].end(),ys);
        sol+=hi-lo;
        return;
    }
    int mij=(st+dr)>>1;
    if(xj<=v[mij].fi)
    query(st,mij,po<<1);
    if(xs>=v[mij+1].fi)
    query(mij+1,dr,(po<<1)+1);
}
int main ()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>v[i].fi>>v[i].se;
    sort(v+1,v+n+1);
    for(i=1;i<=n;++i)
    build(1,n,1);
    for(i=1;i<=n;++i)
        upd(1,n,1);
    f>>m;
    for(i=1;i<=m;++i)
    {
        f>>xj>>yj>>xs>>ys;
        sol=0;
        query(1,n,1);
        g<<sol<<"\n";
    }
    return 0;
}