Advertisement
PikMike

Untitled

Jan 22nd, 2017
413
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.68 KB | None | 0 0
  1. int t[4 * N], upd[4 * N];
  2.  
  3.  
  4. void push(int v){
  5.     upd[v * 2] += upd[v];
  6.     upd[v * 2 + 1] += upd[v];
  7.     t[v] += upd[v];
  8.     upd[v] = 0;
  9. }
  10.  
  11.  
  12. void add(int v, int l, int r, int L, int R, int val){
  13.     push(v);
  14.     if (l >= r || L >= R)
  15.         return;
  16.     if (l == L && r == R){
  17.         upd[v] += val;
  18.         push(v);
  19.         return;
  20.     }
  21.     int m = (l + r) / 2;
  22.     add(v * 2, l, m, L, min(R, m), val);
  23.     add(v * 2 + 1, m, r, max(L, m), R, val);
  24.     t[v] = max(t[v * 2], t[v * 2 + 1]);
  25. }
  26.  
  27.  
  28. int getRg(int v, int l, int r, int val){
  29.     push(v);
  30.     if (l == r - 1)
  31.         return (t[v] >= val ? l : -1);
  32.     int m = (l + r) / 2;
  33.     if (t[v * 2 + 1] >= val)
  34.         return getRg(v * 2 + 1, m, r, val);
  35.     else
  36.         return getRg(v * 2, l, m, val);
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement