fork download
copy 
  1. #include <bits/stdc++.h>
  2. const long long N = 1e12;
  3. struct SegmentTree {
  4.     std::vector<long long> seg_data{0}, mx{N};
  5.     std::vector<int> L{0}, R{0};
  6.  
  7.     void check(int &x, long long rx){
  8.         if(x) return;
  9.         x = (int)seg_data.size();
  10.         seg_data.push_back(0);
  11.         mx.push_back(rx-1);
  12.         L.push_back(0);
  13.         R.push_back(0);
  14.     }
  15.  
  16.     long long get(long long i, long long ni=0, long long lx=-N, long long rx=N+1){
  17.         if(rx - lx == 1)
  18.             return seg_data[ni]+lx;
  19.  
  20.         long long mid = (lx + rx) / 2;
  21.         if(i < mid) {
  22.             check(L[ni], mid);
  23.             return get(i, L[ni], lx, mid) + seg_data[ni];
  24.         }
  25.         check(R[ni], rx);
  26.         return get(i, R[ni], mid, rx)+seg_data[ni];
  27.     }
  28.  
  29.     void add(long long l, long long r, int v, long long ni=0, long long lx=-N, long long rx=N+1) {
  30.  
  31.         if(lx >= l && rx <= r) {
  32.             seg_data[ni] += v;
  33.             mx[ni] += v;
  34.             return;
  35.         }
  36.         if(rx <= l || lx >= r)
  37.             return;
  38.  
  39.         long long mid = (lx + rx) / 2;
  40.         check(L[ni], mid);
  41.         add(l, r, v, L[ni], lx, mid);
  42.         check(R[ni], rx);
  43.         add(l, r, v, R[ni], mid, rx);
  44.  
  45.         mx[ni] = mx[R[ni]]+seg_data[ni];
  46.     }
  47.  
  48.     long long upper_bound(long long x, long long ni=0, long long lx=-N, long long rx=N){
  49.         x -= seg_data[ni];
  50.         if(rx-lx==1)
  51.             return lx > x ? lx : rx;
  52.         long long mid = (lx+rx)/2;
  53.         check(L[ni], mid);
  54.         if(mx[L[ni]] > x)
  55.             return upper_bound(x, L[ni], lx, mid);
  56.         check(R[ni], rx);
  57.         return upper_bound(x, R[ni], mid, rx);
  58.     }
  59. };
  60. int main() {
  61.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  62.     int n, q;
  63.     std::cin >> n >> q;
  64.     SegmentTree st;
  65.     auto add = [&]()->void{
  66.         long long p;
  67.         int a, b;
  68.         std::cin >> p >> a >> b;
  69.         long long l = st.upper_bound(p);
  70.         st.add(-N, l, -b);
  71.         st.add(l, N+1, a);
  72.     };
  73.     while(n--)
  74.         add();
  75.     while(q--){
  76.         int op;
  77.         std::cin >> op;
  78.         if(op == 1)
  79.             add();
  80.         else {
  81.             long long x;
  82.             std::cin >> x;
  83.             std::cout << st.get(x) << '\n';
  84.         }
  85.     }
  86. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
3 3
5 2 1
10 3 4
2 1 5
2 6
1 8 2 3
2 6
stdout
copy 
5
2
https://ideone.com/ImOVdF
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!