Cod sursa(job #1571167)

Utilizator Nevermore10Macovei Cosmin Nevermore10 Data 17 ianuarie 2016 13:33:27
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>

#define DIM 100005

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

int N,M,nr;

vector <int> A[DIM];

struct point{
    int x,y;
};

point P[16005];

int cmp(const point a,const point b){
    return a.x<b.x;
}

void update(int nod,int p,int u){
    if(p==u){
        A[nod].push_back(p);
        return;
    }

    int mid=(p+u)>>1;

    update(2*nod,p,mid);
    update(2*nod+1,mid+1,u);

    int i=0,j=0;

    int a=2*nod;
    int b=2*nod+1;

    while(i < A[a].size() && j < A[b].size()){
        if( P[A[a][i]].y < P[A[b][j]].y ){
            A[nod].push_back(A[a][i]);
            i++;
        }
        else{
            A[nod].push_back(A[b][j]);
            j++;
        }
    }
    for(;i<A[a].size();i++)
        A[nod].push_back(A[a][i]);
    for(;j<A[b].size();j++)
        A[nod].push_back(A[b][j]);
    /*for(int i=0;i<A[nod].size();i++)
        fout << A[nod][i]] << " ";
    fout << "\n";
    */
}
void query(int nod,int p,int u,int a1,int b1,int a2,int b2){
    if(a1 <= P[p].x && P[u].x <= a2){
        int st,dr,mid,poz;
        st=0;
        dr=A[nod].size()-1;
        while(st<=dr){
            mid = (st+dr)>>1;
            if(P[A[nod][mid]].y < b1)
                st=mid+1;
            else
                dr=mid-1;
        }
        poz=st;
        st=0;
        dr=A[nod].size()-1;
        while(st<=dr){
            mid = (st+dr) >> 1;
            if(P[A[nod][mid]].y <= b2)
                st=mid+1;
            else
                dr=mid-1;
        }
        nr+=dr-poz+1;/*
        fout << b1 << " " << b2 << "\n";
        for(int i=0;i<A[nod].size();i++)
            fout << P[A[nod][i]].y << " ";
        fout << "\n";*/

        return;
    }
    int mid=(p+u)>>1;
    if(P[mid].x>=a1)
        query(2*nod,p,mid,a1,b1,a2,b2);
    if(P[mid+1].x<=a2)
        query(2*nod+1,mid+1,u,a1,b1,a2,b2);

}

int main(){

    fin >> N;

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

    sort(P+1,P+N+1,cmp);

    update(1,1,N);

    fin >> M;

    while(M--){
        nr=0;
        int a1,a2,b1,b2;
        fin >> a1 >> b1 >> a2 >> b2;
        if(P[1].x > a2 || P[N].x < a1)
            fout << "0\n";
        else{
            query(1,1,N,a1,b1,a2,b2);
            fout << nr << "\n";
        }

    }

    return 0;

}