Mai intai trebuie sa te autentifici.

Cod sursa(job #1226619)

Utilizator touristGennady Korotkevich tourist Data 6 septembrie 2014 15:25:23
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 16005

using namespace std;

int N;
vector <int> a,aint[3*Nmax];
struct pc
{
    int x,y;
    bool operator < (const pc A) const
    {
        return x<A.x;
    }
};
pc v[Nmax];

inline void Build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod].push_back(v[st].y);
        return;
    }
    int mij=((st+dr)>>1);
    Build(2*nod,st,mij); Build(2*nod+1,mij+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());
}

inline int Query(int nod, int st, int dr, int p1, int p2, int x, int y)
{
    if(st==p1 && p2==dr)
        return upper_bound(aint[nod].begin(),aint[nod].end(),y)-lower_bound(aint[nod].begin(),aint[nod].end(),x);
    int mij=((st+dr)>>1);
    if(p2<=mij)
        return Query(2*nod,st,mij,p1,p2,x,y);
    if(p1>mij)
        return Query(2*nod+1,mij+1,dr,p1,p2,x,y);
    return Query(2*nod,st,mij,p1,mij,x,y)+Query(2*nod+1,mij+1,dr,mij+1,p2,x,y);
}

int main()
{
    int i,M,x1,x2,y1,y2,ind1,ind2;
    freopen ("zoo.in","r",stdin);
    freopen ("zoo.out","w",stdout);
    scanf("%d", &N);
    for(i=1;i<=N;++i)
        scanf("%d%d", &v[i].x,&v[i].y);
    sort(v+1,v+N+1);
    for(i=1;i<=N;++i)
        a.push_back(v[i].x);
    Build(1,1,N);
    scanf("%d", &M);
    while(M--)
    {
        scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
        ind1=lower_bound(a.begin(),a.end(),x1)-a.begin();
        ind2=upper_bound(a.begin(),a.end(),x2)-a.begin()-1;
        printf("%d\n", Query(1,1,N,ind1+1,ind2+1,y1,y2));
    }
    return 0;
}