Cod sursa(job #1153173)

Utilizator Kira96Denis Mita Kira96 Data 25 martie 2014 12:01:53
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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;
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)
        merge(H[po<<1].begin(),H[po<<1].end(),H[(po<<1)+1].begin(),H[(po<<1)+1].end(),H[po].begin());
}
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;
    }
    if(st==dr)
    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;
}