Cod sursa(job #1393906)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 19 martie 2015 20:50:13
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
ifstream f("zoo.in");
const int NMax = 16005;
vector <int> Arb[4*NMax];
pair <int,int> Point[NMax];
int N,M;
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>Point[i].first>>Point[i].second;
    sort(Point+1,Point+N+1);
}

void buildTree(int K,int L,int R)
{
    if(L>R)
        return;
    int Mid=(L+R)/2;
    if(L==R)
    {
        Arb[K].resize(1,Point[L].second);
        return;
    }
    buildTree(2*K,L,Mid);
    buildTree(2*K+1,Mid+1,R);
    Arb[K].resize(Arb[2*K].size()+Arb[2*K+1].size());
    merge(Arb[2*K].begin(),Arb[2*K].end(),Arb[2*K+1].begin(),Arb[2*K+1].end(),Arb[K].begin());
}
int binSearch(int val,int K)
{
    int left=0,mid,right=Arb[K].size()-1,sol=-1;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(Arb[K][mid]>=val)
        {
            sol=mid;
            right=mid-1;
        }
        else
            left=mid+1;
    }
    return sol;
}
int Query(int K,int L,int R,int QX1,int QX2,int QY1,int QY2)
{
    if(L>=R)
        return 0;
    int Mid=(L+R)/2;
    if(QX1<=Point[L].first && Point[R].first<=QX2)
    {
        return lower_bound(Arb[K].begin(),Arb[K].end(),QY2+1)-lower_bound(Arb[K].begin(),Arb[K].end(),QY1);
    }
    if(QX1>Point[Mid].first)
    {
        return Query(2*K+1,Mid+1,R,QX1,QX2,QY1,QY2);
    }
    if(QX2<Point[Mid+1].first)
    {
        return Query(2*K,L,Mid,QX1,QX2,QY1,QY2);
    }
    return Query(2*K+1,Mid+1,R,QX1,QX2,QY1,QY2) + Query(2*K,L,Mid,QX1,QX2,QY1,QY2);
}
int main()
{
    freopen("zoo.out","w",stdout);
    Read();
    buildTree(1,1,N);
    f>>M;
    while(M--)
    {
        int QX1,QX2,QY1,QY2;
        f>>QX1>>QY1>>QX2>>QY2;
        QX1=max(QX1,Point[1].first);
        QX2=min(QX2,Point[N].first);
        printf("%d\n",Query(1,1,N,QX1,QX2,QY1,QY2));
    }
    return 0;
}