Cod sursa(job #1226626)

Utilizator touristGennady Korotkevich tourist Data 6 septembrie 2014 16:10:15
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 16005
#define Lg 1000000
#define verf ++poz==Lg? fin.read(Buffer,Lg), poz=0:0

using namespace std;
ifstream fin ("zoo.in");
int N,poz;
char Buffer[Lg];

inline void read(int &x)
{
    int sign=1;
    for(;!(Buffer[poz]>='0' && Buffer[poz]<='9') && Buffer[poz]!='-';verf);
    if(Buffer[poz]=='-')
    {
        sign=-1; verf;
    }
    for(x=0;Buffer[poz]>='0' && Buffer[poz]<='9';x=x*10+Buffer[poz]-'0',verf);
    x*=sign;
}

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;
    ofstream fout ("zoo.out");
    read(N);
    for(i=1;i<=N;++i)
    {
        read(v[i].x); read(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);
    read(M);
    while(M--)
    {
        read(x1); read(y1); read(x2); read(y2);
        ind1=lower_bound(a.begin(),a.end(),x1)-a.begin();
        ind2=upper_bound(a.begin(),a.end(),x2)-a.begin()-1;
        if(ind1<N && ind2>=0)
            fout<<Query(1,1,N,ind1+1,ind2+1,y1,y2)<<"\n";
    }
    return 0;
}