Cod sursa(job #1456417)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 30 iunie 2015 17:33:42
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 16100
#define inf 2000000010
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int n,m,a1,b1,a2,b2;
int le,ri;
vector <pair<int,int> > vec;
vector <pair<int,int> > :: iterator p,q;
vector <int> aint[nmax*4];

void build(int nod,int st,int dr)
{
    aint[nod].resize(dr-st+1);
    if (st==dr) {
        aint[nod][0]=vec[st].second;
        return;
    }
    int mid=(st+dr)/2;
    build(nod*2,st,mid);
    build(nod*2+1,mid+1,dr);


    int nst=nod*2,ndr=nod*2+1;
    int lst=mid-st+1,ldr=dr-mid;
    int i=0,j=0,k=0;

    while (i<lst&&j<ldr) {
        if (aint[nst][i]<aint[ndr][j])
            aint[nod][k++]=aint[nst][i++];
        else
            aint[nod][k++]=aint[ndr][j++];
    }
    while (i<lst)
        aint[nod][k++]=aint[nst][i++];
    while (j<ldr)
        aint[nod][k++]=aint[ndr][j++];
}
int query(int nod,int st,int dr)
{
    if (dr<le||st>ri||st>dr)
        return 0;
    if (le<=st&&dr<=ri) {
        return upper_bound(aint[nod].begin(),aint[nod].end(),b2)
            -lower_bound(aint[nod].begin(),aint[nod].end(),b1);
    }
    int mid=(st+dr)>>1;
    return query(nod*2,st,mid)+query(nod*2+1,mid+1,dr);
}
int main()
{
    int i,j;
    f>>n;
    vec.resize(n+1);
    for (i=1;i<=n;i++)
        f>>vec[i].first>>vec[i].second;
    sort(vec.begin()+1,vec.end());
    build(1,1,n);
    for (f>>m;m;m--) {
        f>>a1>>b1>>a2>>b2;
        p=lower_bound(vec.begin()+1,vec.end(),make_pair(a1,-inf));
        q=upper_bound(vec.begin()+1,vec.end(),make_pair(a2,inf));q--;
        le=p-vec.begin();
        ri=q-vec.begin();
        g<<query(1,1,n)<<'\n';
    }




    return 0;
}