Cod sursa(job #1835790)

Utilizator LucianTLucian Trepteanu LucianT Data 27 decembrie 2016 14:02:04
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>
#define maxN 16006
using namespace std;
int n,m,i,j,a1,b1,a2,b2;
pair<int,int> points[maxN];
vector<int> arb[4*maxN];
void build(int nod,int st,int dr)
{
    arb[nod].resize(dr-st+1);
    if(st==dr)
    {
        arb[nod][0]=points[st].second;
        return;
    }
    int mij=st+(dr-st)/2;
    build(2*nod,st,mij);
    build(2*nod+1,mij+1,dr);
    int i=0,j=0,k=0;
    int left_size=arb[2*nod].size();
    int right_size=arb[2*nod+1].size();
    while(i<left_size && j<right_size)
        if(arb[2*nod][i]<arb[2*nod+1][j])
            arb[nod][k++]=arb[2*nod][i++];
        else arb[nod][k++]=arb[2*nod+1][j++];
    while(i<left_size)
        arb[nod][k++]=arb[2*nod][i++];
    while(j<right_size)
        arb[nod][k++]=arb[2*nod+1][j++];
}
int query(int nod,int st,int dr)
{
    int start,stop,sol=0;
    if(a1<=points[st].first && points[dr].first<=a2)
    {
        start=lower_bound(arb[nod].begin(),arb[nod].end(),b1)-arb[nod].begin();
        stop=upper_bound(arb[nod].begin(),arb[nod].end(),b2)-arb[nod].begin();
        return stop-start;
    }
    if(st==dr)
        return 0;
    int mij=st+(dr-st)/2;
    if(a1<=points[mij].first)
        sol+=query(2*nod,st,mij);
    if(points[mij+1].first<=a2)
        sol+=query(2*nod+1,mij+1,dr);
    return sol;
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d %d",&points[i].first,&points[i].second);
    sort(points+1,points+n+1);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
        scanf("%d %d %d %d",&a1,&b1,&a2,&b2),
        printf("%d\n",query(1,1,n));
    return 0;
}