Cod sursa(job #1581704)

Utilizator aetherAlexandra Vanca aether Data 27 ianuarie 2016 03:06:45
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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());
    merge(aint[2*nod].begin(),aint[2*nod].end(),aint[2*nod+1].begin(),aint[2*nod+1].end(),aint[nod].begin());
}
int query(int nod,int st,int dr,int x1,int y1,int x2,int y2)
{
    if(x1<=st && dr<=x2)
    {
        int A=upper_bound(aint[nod].begin(),aint[nod].end(),y2)-aint[nod].begin();
        int B=lower_bound(aint[nod].begin(),aint[nod].end(),y1)-aint[nod].begin();
        return A-B;
    }
    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);
        x1=lower_bound(X.begin(),X.end(),x1)-X.begin()+1;
        x2=upper_bound(X.begin(),X.end(),x2)-X.begin();
        printf("%d\n",query(1,1,n,x1,y1,x2,y2));
    }
    return 0;
}