Cod sursa(job #2393332)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 31 martie 2019 12:47:25
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

typedef pair<int, int> Point;

vector <pair<int,int>> pct;
int n,m,x1,y1,x2,y2;
vector <int> arbint[4*16005], aux;

void construieste(int st = 1, int dr = n, int pos = 1){
    if(st==dr){
        arbint[pos].push_back(pct[st].second);
        arbint[pos].resize(1);
        return ;
    }
    int mij = (st+dr)/2;
    construieste(st,mij,2*pos);
    construieste(mij+1,dr,2*pos+1);
    arbint[pos] = vector<int>(arbint[2*pos].size()+arbint[2*pos+1].size());
    merge(arbint[2*pos].begin(),arbint[2*pos].end(),
            arbint[2*pos+1].begin(),arbint[2*pos+1].end(),
            arbint[pos].begin());
}

int cauta(int qst, int qdr, int st = 1, int dr = n, int pos = 1){
    if(qst<=st && dr<=qdr)
        return upper_bound(arbint[pos].begin(),arbint[pos].end(),y2)-
                lower_bound(arbint[pos].begin(),arbint[pos].end(),y1);
    int mij = (st+dr)/2;
    if(qdr<=mij)
        return cauta(qst,qdr,st,mij,2*pos);
    if(qst>mij)
        return cauta(qst,qdr,mij+1,dr,2*pos+1);
    return cauta(qst,qdr,st,mij,2*pos)+
            cauta(qst,qdr,mij+1,dr,2*pos+1);
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);

    scanf("%d", &n);
    pct = vector<pair<int,int>>(n+1);
    aux = vector <int> (n+1);
    for(int i=1;i<=n;++i)
        scanf("%d%d", &pct[i].first, &pct[i].second);
    sort(pct.begin()+1,pct.end());
    construieste();
    for(int i=1;i<=n;++i)
        aux[i]=pct[i].first;
    /*
    for(int i=1;i<=9;++i){
        for(int j : arbint[i])
            cout<<j<<" ";
        cout<<"\n";
    }
    */
    scanf("%d", &m);
    for(int i=0;i<m;++i){
        scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
        int st = lower_bound(aux.begin()+1,aux.end(),x1)-aux.begin();
        int dr = upper_bound(aux.begin()+1,aux.end(),x2)-aux.begin()-1;
        //cout<<st<<" "<<dr<<"\n";
        if(dr<st)
            swap(dr,st);
        cout<<cauta(st,dr)<<"\n";
    }
    return 0;
}