Cod sursa(job #2393078)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 30 martie 2019 19:29:35
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 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];

bool cmp(const pair<int,int> &p1, const int v)
{
    if(p1.first<=v)
        return true;
    else
        return false;
}

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, ret = 0;
    if(qst<=mij)
        ret+=cauta(qst,qdr,st,mij,2*pos);
    if(qdr>mij)
        ret+=cauta(qst,qdr,mij+1,dr,2*pos+1);
    return ret;
}

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

    scanf("%d", &n);
    pct = vector<pair<int,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<=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);
        if(x1>pct[n].first || x2<pct[1].first)
		{
			cout<<"0\n";
			continue;
		}
        int st = lower_bound(pct.begin()+1,pct.end(),Point(x1,y1))-pct.begin();
        int dr = upper_bound(pct.begin()+1,pct.end(),Point(x2,y2))-pct.begin();
        //cout<<st<<" "<<dr<<"\n";
        cout<<cauta(st,dr)<<"\n";
    }
    return 0;
}