Cod sursa(job #2961352)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 6 ianuarie 2023 12:21:04
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

////////////////////////////////////////////

//ifstream cin("zoo.in");
//ofstream cout("zoo.out");

const int MAX = 16e3 + 1;

pair <long long,long long> puncte[MAX];

vector <long long> aint[4*MAX];

vector <long long> lista[MAX];

vector <long long> ox;

int n , q , x1 , y1 , x2 , y2;

/////////////////////////////////////////////

void init(int nod , int st , int dr){

    if(st == dr){

        swap(aint[nod],lista[st]);

    }else{

        int mij = (st+dr)/2;

        init(nod*2,st,mij);
        init(nod*2+1,mij+1,dr);

        merge(  aint[nod*2].begin(), aint[nod*2].end() ,
                aint[nod*2+1].begin() , aint[nod*2+1].end(),
                back_inserter(aint[nod]));
    }

}

long long query( int nod , int st , int dr , int qst , int qdr , int a , int b){

    if( qst <= st && dr <= qdr ){

        return upper_bound(aint[nod].begin(),aint[nod].end(),b) -
        lower_bound(aint[nod].begin(),aint[nod].end(),a);
    }

    int mij = (st+dr)/2;

    int val = 0;

    if(qst <= mij) val += query(nod*2,st,mij,qst,qdr,a,b);
    if(qdr >= (mij+1)) val += query(nod*2+1,mij+1,dr,qst,qdr,a,b);

    return val;

}

int main()
{

    cin >> n;

    for(int i = 1 ; i <= n ; i++){

        cin >> puncte[i].first >> puncte[i].second;

    }

    sort(puncte + 1, puncte + 1 + n);

    puncte[0].first = -2e9 - 1;

    int k = 0;

    for(int i = 1 ; i <= n ; i++){

        if( puncte[i].first != (puncte[i-1].first) ){

            lista[++k].push_back(puncte[i].second);

            ox.push_back(puncte[i].first);

        }else lista[k].push_back(puncte[i].second);
    }

    for(int i = 1 ; i <= k ; i++) sort(lista[i].begin(),lista[i].end());

    init(1,1,k);

    // query

    cin >> q;

    while(q--){

        cin >> x1 >> y1 >> x2 >> y2;

        int a = lower_bound(ox.begin(),ox.end(), x1) - ox.begin();

        int b = upper_bound(ox.begin(),ox.end(), x2) - ox.begin() - 1;

        a++;

        b++;

        cout << query(1,1,k,a,b,y1,y2) << '\n';
    }

    return 0;
}