Submission #74609036

---

Source Code Expand

#include <iostream>
#include <vector>
#include<map>
using namespace std;

#define int long long
const int inf = 1e18;

struct node{
    vector<int> val;
};

class SegTree{
    private:

        int n;
        vector<node> tree;
        vector<vector<int>> arr;

    public:

    SegTree(int n, vector<vector<int>> arr){
        this->n = n;
        this->arr = arr;

        tree.resize(4 * n);

        build(0, 0, n - 1);
    }

    node combine(node x, node y){
        node temp;

        auto &p = x.val;
        auto &q = y.val;

        int szp = (int)p.size();
        int szq = (int)q.size();

        int i = 0, j = 0;
        vector<int> curr;
        while(i < szp && j < szq){

            if(p[i] < q[j]){
                curr.push_back(p[i]);
                i++;
            }else{
                curr.push_back(q[j]);
                j++;
            }
        }

        while(i < szp){
            curr.push_back(p[i]);
            i++;
        }

        while(j < szq){
            curr.push_back(q[j]);
            j++;
        }

        temp.val = curr;

        return temp;
    }

    void build(int idx, int st, int end){

        if(st == end){
            tree[idx].val = arr[st];
            return;
        }

        int mid = (st + end) / 2;
    
        build(idx * 2 + 1, st, mid);
        build(idx * 2 + 2, mid + 1, end);

        tree[idx] = combine(tree[idx * 2 + 1], tree[idx * 2 + 2]);
    }

    int query(int l, int r, int num, int idx, int st, int end){

        if(l > end || r < st){
            return 0;
        }

        if(l <= st && r >= end){

            auto &p = tree[idx].val;

            if(p.empty()) return 0;
            if(p.back() < num) return 0;

            int L = 0, R = (int)p.size() - 1;
            int ans = -1;
            while(L <= R){
                int mid = (L + R) / 2;

                if(p[mid] >= num){
                    R = mid - 1;
                    ans = mid;
                }else{
                    L = mid + 1;
                }
            }
            return (int)p.size() - ans;
        }

        int mid = (st + end) / 2;

        int lans = query(l, r, num, idx * 2 + 1, st, mid);
        int rans = query(l, r, num, idx * 2 + 2, mid + 1, end);

        return lans + rans;
    }

    int getAns(int l, int r, int num){
        return query(l, r, num, 0, 0, n - 1);
    }

};

void solve(){
    int n, m, q, k;
    cin >> n >> m >> q >> k;

    vector<vector<int>> arr(n);
    for(int i = 1; i <= m; i++){
        int idx, val;
        cin >> idx >> val;
        idx--;

        arr[idx].push_back(val);
    }
    for(int i = 0; i < n; i++){
        sort(arr[i].begin(), arr[i].end());
    }

    SegTree sgt(n, arr);

    while(q--){
        int l, r, num;
        cin >> l >> r >> num;
        l--; r--;

        int ans = sgt.getAns(l, r, num);

        cout << max(0LL, ans - k) << endl;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc = 1; //cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

Submission Info

Judge Result