Submission #74603701

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;
int a[N], idx, root[N], l[N], r[N], T[N];
struct Node{
    int ls, rc;
    int cnt;
}tr[N * 20];
int build(int l,int r){
    int p = idx ++;
    tr[p].ls = tr[p].rc = tr[p].cnt = 0;
    if(l == r)
        return p;
    int mid = l + r >> 1;

    tr[p].ls = build(l, mid);
    tr[p].rc = build(mid + 1, r);

    return p;
}
vector<int> num;
int find(int x){
    return lower_bound(num.begin(), num.end(), x) - num.begin() + 1;
}
void Insert(int x,int& y,int l,int r,int v){
    int id = idx ++;
    tr[id] = tr[x];
    tr[id].cnt += 1;
    y = id;
    if(l == r){
        return;
    }
    int mid = l + r >> 1;
    if(v <= mid) Insert(tr[x].ls, tr[y].ls, l, mid, v);
    else Insert(tr[x].rc, tr[y].rc, mid + 1, r, v);

}
int query(int Root,int l1,int r1,int l2,int r2){
    if(l1 >= l2 && r1 <= r2){
        return tr[Root].cnt;
    }

    int mid = l1 + r1 >> 1;
    int res = 0;

    if(l2 <= mid) res += query(tr[Root].ls, l1, mid, l2, r2);
    if(r2 > mid) res += query(tr[Root].rc, mid + 1, r1, l2, r2);

    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
        
    int n, m, q, k; cin >> n >> m >> q >> k;
    
    vector<vector<int>> pos(n + 1);

    while(m -- ){  
        int s, d; cin >> s >> d;
        pos[s].push_back(d);
        num.push_back(d);
    }

    for(int i = 1;i <= q;i ++ ){
        cin >> l[i] >> r[i] >> T[i];
        num.push_back(T[i]);
    }

    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());

    root[0] = build(1, num.size());

    for(int i = 1;i <= n;i ++ ){
        root[i] = root[i - 1];
        for(auto val : pos[i]){
            Insert(root[i], root[i], 1, num.size(), find(val));
        }
    }
    n = num.size();
    for(int i = 1;i <= q;i ++ ){
        int L = l[i], R = r[i], val = find(T[i]);
        L --;
        cout << max(query(root[R], 1, n, val, n) - query(root[L], 1, n, val, n) - k, 0) << "\n";
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int build(int, int)':
./Main.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
./Main.cpp: In function 'void Insert(int, int&, int, int, int)':
./Main.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = l + r >> 1;
      |               ~~^~~
./Main.cpp: In function 'int query(int, int, int, int, int)':
./Main.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = l1 + r1 >> 1;
      |               ~~~^~~~

Judge Result