Cod sursa(job #1222965)

Utilizator atatomirTatomir Alex atatomir Data 24 august 2014 20:58:37
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<long,long> Point;

#define maxN 16010
#define maxM 100010
#define x first
#define y second
#define leftSon (nod << 1)
#define rightSon ((nod << 1)|1)
#define pb push_back

long n,m,i;
vector<long> aint[maxN << 2];
Point p[maxN],p1,p2;

bool cmp(const Point& a,const Point& b){
    return a.x < b.x;
}

void BuildAInt(long nod,long L,long R){
    if(L == R){
        aint[nod].pb(p[L].y);
        return;
    }
    long M = (L+R) >> 1;
    BuildAInt(leftSon,L,M);
    BuildAInt(rightSon,M+1,R);

    long left=leftSon,right=rightSon,posl=0,posr=0;
    long mini,minim;
    while((posl<aint[left].size())&&(posr<aint[right].size())){
        mini = 1; minim = aint[left][posl];
        if(minim > aint[right][posr]){
            mini = 2; minim = aint[right][posr];
        }
        aint[nod].pb(minim);
        if(mini == 1) posl++; else posr++;
    }
    while(posl<aint[left].size()) aint[nod].pb(aint[left][posl++]);
    while(posr<aint[right].size()) aint[nod].pb(aint[right][posr++]);
}

long cbL(long src){
    long i=1,j=n,m;
    do {
        m = (i+j) >> 1;
        if(src <= p[m].x)
            j = m-1;
        else
            i = m+1;
    }   while(i<=j);
    return i;
}

long cbR(long src){
    long i=1,j=n,m;
    do {
        m = (i+j) >> 1;
        if(src < p[m].x)
            j = m-1;
        else
            i = m+1;
    }   while(i<=j);
    return j;
}

long cbnL(long nod,long src){
    long i=0,j=aint[nod].size()-1,m;
    do {
        m = (i+j) >> 1;
        if(src <= aint[nod][m])
            j = m-1;
        else
            i = m+1;
    }   while(i<=j);
    return i;
}

long cbnR(long nod,long src){
    long i=0,j=aint[nod].size()-1,m;
    do {
        m = (i+j) >> 1;
        if(src < aint[nod][m])
            j = m-1;
        else
            i = m+1;
    }   while(i<=j);
    return j;
}

long check(long nod,long L,long R){
    L = cbnL(nod,L);
    R = cbnR(nod,R);
    return R-L+1;
}

long Query(long nod,long L,long R,long qL,long qR){
    if(qL <= L && R <= qR){
        return check(nod,p1.y,p2.y);
    }
    long M = (L+R) >> 1,ans=0;
    if(qL <= M) ans += Query(leftSon,L,M,qL,qR);
    if(qR >  M) ans += Query(rightSon,M+1,R,qL,qR);
    return ans;
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);

    scanf("%ld",&n);
    for(i=1;i<=n;i++) scanf("%ld %ld",&p[i].x,&p[i].y);
    sort(p+1,p+n+1,cmp);

    BuildAInt(1,1,n);

    scanf("%ld",&m);
    for(i=1;i<=m;i++){
        scanf("%ld %ld %ld %ld",&p1.x,&p1.y,&p2.x,&p2.y);
        p1.x = cbL(p1.x);
        p2.x = cbR(p2.x);
        printf("%ld\n",Query(1,1,n,p1.x,p2.x));
    }

    return 0;
}