Cod sursa(job #2956519)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 19 decembrie 2022 18:27:26
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.2 kb
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

const int nmax = 16e3;

int n, m;

using Pii = pair<int, int>;
using segNode = vector<short>;

vector <int> nrmX, nrmY;

Pii pct[nmax + 2];


int cautaRange(vector <short> & vec, int lQ, int rQ){
    if(vec.size() == 0)
        return 0;
    int l, r, ans1, ans2;
    l = 0, r = vec.size() - 1, ans1 = 0;
    while(l <= r){
        int mij = (l + r) / 2;
        if(vec[mij] >= lQ)
            ans1 = mij, r = mij - 1;
        else
            l = mij + 1;
    }

    l = 0, r = vec.size() - 1, ans2 = vec.size();

    while(l <= r){
        int mij = (l + r) / 2;
        if(vec[mij] <= rQ)
            ans2 = mij, l = mij + 1;
        else
            r = mij - 1;
    }

    return ans2 - ans1 + 1;
}

struct segTree{
private:
    int len;
    vector <segNode> seg;
public:
    segTree(Pii * pct, int n){
        len = nrmX.size();
        seg.resize(2 * len);
        build(0, 0, len - 1, pct, n);
    }
    int rangeQuery(short xx1, short yy1, short xx2, short yy2){
        return queryUtil(0, 0, len - 1, xx1, xx2, yy1, yy2);
    }
private:
    int queryUtil(int p, int l, int r, int lQ, int rQ, int llQ, int rrQ){
        if(lQ <= l && r <= rQ)
            return cautaRange(seg[p], llQ, rrQ);
        int mij = (l + r) / 2;
        if(lQ <= mij && mij + 1 <= rQ)
            return queryUtil(p + 1, l, mij, lQ, rQ, llQ, rrQ) + queryUtil(p + 2 * (mij - l + 1), mij + 1, r, lQ, rQ, llQ, rrQ);
        else if(lQ <= mij)
            return queryUtil(p + 1, l, mij, lQ, rQ, llQ, rrQ);
        else
            return queryUtil(p + 2 * (mij - l + 1), mij + 1, r, lQ, rQ, llQ, rrQ);
    }
    void build(int p, int l, int r, Pii * pct, int n){
        if(l == r){
            seg[p].resize(n);
            for(int i = 0; i < n; i++)
                seg[p][i] = pct[i].second;
            return;
        }
    
        int mij = (l + r) / 2;
        int lst = 0;
        for(int i = 0; i < n; i++)
            if(pct[i].first <= mij)
                lst = i + 1;
            else
                break;
        
        build(p + 1, l, mij, pct, lst);
        build(p + 2 * (mij - l + 1), mij + 1, r, pct + lst, n - lst);
        seg[p].resize(n);
        merge(seg[p + 1].begin(), seg[p + 1].end(), seg[p + 2 * (mij - l + 1)].begin(), seg[p + 2 * (mij - l + 1)].end(), seg[p].begin());
    }
};


void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        pct[i] = make_pair(x, y);
        nrmX.push_back(x);
        nrmY.push_back(y);
    }
    sort(nrmX.begin(), nrmX.end());
    nrmX.erase(unique(nrmX.begin(), nrmX.end()), nrmX.end());
    sort(nrmY.begin(), nrmY.end());
    nrmY.erase(unique(nrmY.begin(), nrmY.end()), nrmY.end());

    // for(int i = 1; i <= n; i++)
    //     cerr << pct[i].first << " " << pct[i].second << "\n";
    // cerr << "\n";

    for(int i = 1; i <= n; i++)
        pct[i] = make_pair(lower_bound(nrmX.begin(), nrmX.end(), pct[i].first) - nrmX.begin(), lower_bound(nrmY.begin(), nrmY.end(), pct[i].second) - nrmY.begin());

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

    segTree arb(pct + 1, n);
    // arb.showAll();
    cin >> m;
    for(int i = 1; i <= m; i++){
        int xx1, yy1, xx2, yy2;
        cin >> xx1 >> yy1 >> xx2 >> yy2;
        int pxx1 = lower_bound(nrmX.begin(), nrmX.end(), xx1) - nrmX.begin();
        int pxx2 = upper_bound(nrmX.begin(), nrmX.end(), xx2) - nrmX.begin();
        int pyy1 = lower_bound(nrmY.begin(), nrmY.end(), yy1) - nrmY.begin();
        int pyy2 = upper_bound(nrmY.begin(), nrmY.end(), yy2) - nrmY.begin();

        // cerr << pxx1 << " " << pyy1 << " " << pxx2 << " " << pyy2 << "\n";

        if(pxx2 == 0 || pyy2 == 0 || pxx1 == nrmX.size() || pyy1 == nrmY.size()){
            cout << "0\n";
            continue;
        }
        pxx2--, pyy2--;
        cout << arb.rangeQuery(pxx1, pyy1, pxx2, pyy2) << "\n";
    }

}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    int q = 1;
    // cin >> q;
    while(q--){
        solve();
    }

    return 0;
}