fork download
copy 
  1. #include <bits/stdc++.h>
  2. const long long inf = 1e17;
  3. struct SegmentTree {
  4.     struct Node {
  5.         long long val;
  6.         long long lazy;
  7.         bool is_lazy;
  8.         explicit Node(long long x = -inf) {
  9.             val = x;
  10.             lazy = 0;
  11.             is_lazy = false;
  12.         }
  13.         void change(long long x) {
  14.             val += x;
  15.             lazy += x;
  16.             is_lazy = true;
  17.         }
  18.     };
  19.     int tree_size;
  20.     std::vector<Node> seg_data;
  21.  
  22.     explicit SegmentTree(int n) {
  23.         tree_size = 1;
  24.         while (tree_size < n) tree_size *= 2;
  25.         seg_data.assign(2 * tree_size, Node());
  26.     }
  27.  
  28.     static Node merge(const Node &lf, const Node & ri) {
  29.         Node ans = Node();
  30.         ans.val = std::max(lf.val, ri.val);
  31.         return ans;
  32.     }
  33.  
  34.     void propagate(int ni, int lx, int rx) {
  35.         if(!seg_data[ni].is_lazy || rx - lx == 1) return;
  36.  
  37.         seg_data[ 2 * ni + 1].change(seg_data[ni].lazy);
  38.         seg_data[ 2 * ni + 2].change(seg_data[ni].lazy);
  39.  
  40.         seg_data[ni].lazy = 0;
  41.         seg_data[ni].is_lazy = false;
  42.     }
  43.  
  44.     void Build(std::vector<long long> &arr, int ni, int lx, int rx) {
  45.         if(rx - lx == 1) {
  46.             if(lx < (int)arr.size())
  47.                 seg_data[ni] = Node(arr[lx]);
  48.             else
  49.                 seg_data[ni] = Node(inf);
  50.             return;
  51.         }
  52.         int mid = (lx + rx) / 2;
  53.         Build(arr, 2 * ni + 1, lx, mid);
  54.         Build(arr, 2 * ni + 2, mid, rx);
  55.  
  56.         seg_data[ni] = merge(seg_data[2 * ni + 1], seg_data[2 * ni + 2]);
  57.     }
  58.     void Build(std::vector<long long> & arr) {
  59.         Build(arr, 0, 0, tree_size);
  60.     }
  61.  
  62.     Node get(int i, int ni, int lx, int rx){
  63.         propagate(ni, lx, rx);
  64.         if(rx - lx == 1)
  65.             return seg_data[ni];
  66.  
  67.         int mid = (lx + rx) / 2;
  68.         if(i < mid)
  69.             return get(i, ni*2+1, lx, mid);
  70.         else
  71.             return get(i, ni*2+2, mid, rx);
  72.     }
  73.     long long get(int i) {
  74.         return get(i, 0, 0, tree_size).val;
  75.     }
  76.  
  77.  
  78.     void add(int l, int r, int v, int ni, int lx, int rx) {
  79.         propagate(ni, lx, rx);
  80.  
  81.         if(lx >= l && rx <= r) {
  82.             seg_data[ni].change(v);
  83.             return;
  84.         }
  85.         if(rx <= l || lx >= r)
  86.             return;
  87.  
  88.         int mid = (lx + rx) / 2;
  89.         add(l, r, v, 2 * ni + 1, lx, mid);
  90.         add(l, r, v, 2 * ni + 2, mid, rx);
  91.  
  92.         seg_data[ni] = merge(seg_data[2 * ni + 1], seg_data[2*ni + 2]);
  93.     }
  94.  
  95.     void add(int l, int r, int v) {
  96.         add(l, r, v, 0, 0, tree_size);
  97.     }
  98.  
  99.     int upper_bound(long long x, int ni, int lx, int rx){
  100.         propagate(ni, lx, rx);
  101.  
  102.         if(rx-lx==1)
  103.             return (seg_data[ni].val>x?lx:rx);
  104.  
  105.         int mid = (lx+rx)/2;
  106.         if(seg_data[ni*2+1].val > x)
  107.             return upper_bound(x, ni*2+1, lx, mid);
  108.         else
  109.             return upper_bound(x, ni*2+2, mid, rx);
  110.     }
  111.  
  112.     int upper_bound(long long x){
  113.         return upper_bound(x, 0, 0, tree_size);
  114.     }
  115. };
  116. struct Query{
  117.     int op, a, b;
  118.     long long x, p;
  119. };
  120. int main() {
  121.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  122.     int n, q;
  123.     std::cin >> n >> q;
  124.     Query b[n+q];
  125.     for(int i=0; i<n; ++i)
  126.         std::cin >> b[i].p >> b[i].a >> b[i].b, b[i].op = 1;
  127.     std::vector<long long> numbers;
  128.     std::map<long long, int> flatten;
  129.     for(int j=n; j-n<q; ++j){
  130.         std::cin >> b[j].op;
  131.         if(b[j].op == 1)
  132.             std::cin >> b[j].p >> b[j].a >> b[j].b;
  133.         else {
  134.             std::cin >> b[j].x;
  135.             numbers.push_back(b[j].x);
  136.         }
  137.     }
  138.     std::sort(numbers.begin(), numbers.end());
  139.     numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end());
  140.     int m = numbers.size();
  141.     for(int c=0; c<m; ++c)
  142.         flatten[numbers[c]] = c;
  143.     SegmentTree st(m);
  144.     st.Build(numbers);
  145.     for(int j=0; j<q+n; ++j) {
  146.         if(b[j].op == 1){
  147.             int l = st.upper_bound(b[j].p);
  148.             st.add(0, l, -b[j].b);
  149.             st.add(l, m, b[j].a);
  150.         }
  151.         else{
  152.             std::cout << st.get(flatten[b[j].x]) << '\n';
  153.         }
  154.     }
  155. }
Success #stdin #stdout 0.01s 5320KB
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/4hf1at
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!