SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define INF 1e9
  6.  
  7. long long t[400004], val[400004], a[100000];
  8.  
  9. void build(int v, int lt, int rt) {
  10.     if (lt == rt)
  11.         t[v] = a[lt];
  12.     else {
  13.         int mt=(lt+rt)/2;
  14.         build(2*v, lt, mt);
  15.         build(2*v+1, mt+1, rt);
  16.         t[v] = max(t[2*v], t[2*v+1]);
  17.     }
  18. }
  19.  
  20. void push(int v) {
  21.     if (val[v] > 0) {
  22.         t[2*v] += val[v];
  23.         t[2*v+1] += val[v];
  24.         val[2*v] += val[v];
  25.         val[2*v+1] += val[v];
  26.         val[v] = 0;
  27.     }
  28. }
  29.  
  30. int get(int v, int lt, int rt, int l, int r) {
  31.     if (l > r)
  32.         return -INF;
  33.  
  34.     if (l==lt && r==rt)
  35.         return t[v];
  36.  
  37.     push(v);
  38.  
  39.     int mt=(lt+rt)/2;
  40.     return max(
  41.                 get(2*v, lt, mt, l, min(mt, r)),
  42.                 get(2*v+1, mt+1, rt, max(l, mt+1), r)
  43.            );
  44. }
  45.  
  46. void update(int v, int lt, int rt, int l, int r, int x) {
  47.     if (l > r)
  48.         return;
  49.  
  50.     if (l==lt && r==rt) {
  51.         t[v] += x;
  52.         val[v] += x;
  53.         return;
  54.     }
  55.  
  56.     push(v);
  57.  
  58.     int mt=(lt+rt)/2;
  59.     update (v*2, lt, mt, l, min(r, mt), x);
  60.     update (v*2+1, mt+1, rt, max(l, mt+1), r, x);
  61.     t[v] = max(t[2*v], t[2*v+1]);
  62. }
  63.  
  64. int main() {
  65.     int n=0;  cin >> n;
  66.  
  67.     for (int i=0; i<n; i++)
  68.         cin >> a[i];
  69.  
  70.     build(1, 0, n-1);
  71.  
  72.     int m=0; cin >> m;
  73.  
  74.     vector<long long> ans;
  75.  
  76.     for (int i=0; i<m; i++) {
  77.         char ch; cin >> ch;
  78.         if (ch == 'm') {
  79.             int l=0, r=0; cin >> l >> r;
  80.             ans.push_back(get(1, 0, n-1, l-1, r-1));
  81.         } else {
  82.             int l=0, r=0, x=0; cin >> l >> r >> x;
  83.             update(1, 0, n-1, l-1, r-1, x);
  84.         }
  85.     }
  86.     for (long long i: ans)
  87.         cout << i << ' ';
  88. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top