Cod sursa(job #1904438)

Utilizator OGEastBullOG EastBull OGEastBull Data 5 martie 2017 15:46:37
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int nmax = 16005;
int N,M;

struct point
{
    int x,y;
    bool operator < (const point &A) const
    {
        return x < A.x;
    }
};
point v[nmax];

vector < int > a,aint[4*nmax];


inline void Read()
{
    int i;
    fin >> N;
    for(i = 1; i <= N; i++)
    {
        fin >> v[i].x >> v[i].y;
    }
}

inline void Build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod].push_back(v[st].y);
        return;
    }
    int mid = (st + dr)>>1;
    Build(2*nod,st,mid);
    Build(2*nod+1,mid+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(p1 <= st && dr <= p2)
        return upper_bound(aint[nod].begin(),aint[nod].end(),y) - lower_bound(aint[nod].begin(),aint[nod].end(),x);
    int mid = (st + dr) >> 1, sol1 = 0, sol2 = 0;
    if(p1 <= mid) sol1 = Query(2*nod,st,mid,p1,p2,x,y);
    if(p2 > mid) sol2 = Query(2*nod+1,mid+1,dr,p1,p2,x,y);
    return sol1+sol2;
}


inline void Solve()
{
    int i,x1,x2,y1,y2,ind1,ind2;
    sort(v+1,v+N+1);
    for(i = 1; i <= N; i++) a.push_back(v[i].x);
    Build(1,1,N);
    fin >> M;
    while(M--)
    {
        fin >> 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;
        if(ind1 < N && ind2 >= 0)
            fout << Query(1,1,N,ind1+1,ind2+1,y1,y2) << "\n";
        else fout << "0\n";
    }
}


int main()
{
    Read();
    Solve();
    return 0;
}