Cod sursa(job #1778541)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 13 octombrie 2016 21:25:04
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
# include <fstream>
# include <vector>
# include <algorithm>
# define DIM 16010
# define f first
# define s second
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
vector <pair<int,int> > a[4*DIM];
pair <int,int> v[2*DIM];
int n,m,i,j,k,p,u,x1,x2,y1,y2,pas,sol;
void build(int nod,int st,int dr){
    if(st==dr){
        k++;
        a[nod].push_back(make_pair(v[k].f,v[k].s));
    }
    else{
        int mij=(st+dr)/2;
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);
        int i=0,j=0;
        while(i<a[2*nod].size()&&j<=a[2*nod+1].size())
            if(a[2*nod][i].s<a[2*nod+1][j].s){
                a[nod].push_back(make_pair(a[2*nod][i].f,a[2*nod][i].s));
                i++;
            }
            else{
                a[nod].push_back(make_pair(a[2*nod+1][j].f,a[2*nod+1][j].s));
                j++;
            }
        for(;i<a[2*nod].size();i++)
            a[nod].push_back(make_pair(a[2*nod][i].f,a[2*nod][i].s));
        for(;j<a[2*nod+1].size();j++)
            a[nod].push_back(make_pair(a[2*nod+1][j].f,a[2*nod+1][j].s));
    }
}
void query(int nod,int st,int dr,int p,int u){
    if(p<=st&&u>=dr){
        int j,p1,u1;
        for(pas=1;2*pas<=a[nod].size();pas*=2);
        for(j=-1;pas;pas/=2)
            if(j+pas<a[nod].size())
                if(a[nod][j+pas].s<y1)
                    j+=pas;
        p1=j+1;
        for(pas=1;2*pas<=a[nod].size();pas*=2);
        for(j=-1;pas;pas/=2)
            if(j+pas<a[nod].size())
                if(a[nod][j+pas].s<=y2)
                    j+=pas;
        u1=j;
        sol+=u1-p1+1;
    }
    else{
        int mij=(st+dr)/2;
        if(p<=mij)
            query(2*nod,st,mij,p,u);
        if(u>mij)
            query(2*nod+1,mij+1,dr,p,u);
    }
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i].f>>v[i].s;
    sort(v+1,v+n+1);
    build(1,1,n);
    fin>>m;
    for(i=1;i<=m;i++){
        fin>>x1>>y1>>x2>>y2;
        for(pas=1;2*pas<=n;pas*=2);
        for(j=0;pas;pas/=2)
            if(v[j+pas].f<x1&&j+pas<=n)
                j+=pas;
        p=j+1;
        for(pas=1;2*pas<=n;pas*=2);
        for(j=0;pas;pas/=2)
            if(v[j+pas].f<=x2&&j+pas<=n)
                j+=pas;
        u=j;
        sol=0;
        query(1,1,n,p,u);
        fout<<sol<<"\n";
    }
    return 0;
}