Cod sursa(job #1033102)

Utilizator dariusdariusMarian Darius dariusdarius Data 16 noiembrie 2013 14:28:23
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
using namespace std;
pair<int,int> a[16005];
vector<int> aint[16*16005],X;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod].assign(1,a[st].second);
        return;
    }
    int med=(st+dr)/2;
    build(2*nod,st,med);
    build(2*nod+1,med+1,dr);
    aint[nod].resize(aint[2*nod].size()+aint[2*nod+1].size());
    int l1=0,l2=0;
    for(int i=0;i<(int)aint[nod].size();i++)
        if(l2==(int)aint[2*nod+1].size() || (l1<(int)aint[2*nod].size() && aint[2*nod][l1]<aint[2*nod+1][l2]))
            aint[nod][i]=aint[2*nod][l1++];
        else
            aint[nod][i]=aint[2*nod+1][l2++];
}
int query(int nod,int st,int dr,int x1,int y1,int x2,int y2)
{
    if(x1<=st && dr<=x2)
        return upper_bound(aint[nod].begin(),aint[nod].end(),y2)-lower_bound(aint[nod].begin(),aint[nod].end(),y1);
    int ans=0,med=(st+dr)/2;
    if(x1<=med)
        ans+=query(2*nod,st,med,x1,y1,x2,y2);
    if(med<x2)
        ans+=query(2*nod+1,med+1,dr,x1,y1,x2,y2);
    return ans;
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].first,&a[i].second);
        X.push_back(a[i].first);
    }
    sort(X.begin(),X.end());
    sort(a+1,a+n+1);
    scanf("%d",&m);
    build(1,1,n);
    for(int x1,y1,x2,y2,i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",query(1,1,n,lower_bound(X.begin(),X.end(),x1)-X.begin()+1,y1,upper_bound(X.begin(),X.end(),x2)-X.begin(),y2));
    }
    return 0;
}