SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 46 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[2*v+1] = val[v];
  25.         val[v] = 0;
  26.     }
  27. }
  28.  
  29. int get(int v, int lt, int rt, int l, int r) {
  30.     if (l > r)
  31.         return -INF;
  32.  
  33.     if (l==lt && r==rt)
  34.         return t[v];
  35.  
  36.     push(v);
  37.  
  38.     int mt=(lt+rt)/2;
  39.     return max(
  40.                 get(2*v, lt, mt, l, min(mt, r)),
  41.                 get(2*v+1, mt+1, rt, max(l, mt+1), r)
  42.            );
  43. }
  44.  
  45. void update(int v, int lt, int rt, int l, int r, int x) {
  46.     if (l > r)
  47.         return;
  48.  
  49.     if (l==lt && r==rt) {
  50.         t[v] += x;
  51.         val[v] = x;
  52.         return;
  53.     }
  54.  
  55.     push(v);
  56.  
  57.     int mt=(lt+rt)/2;
  58.     update (v*2, lt, mt, l, min(r, mt), x);
  59.     update (v*2+1, mt+1, rt, max(l, mt+1), r, x);
  60.     t[v] = max(t[2*v], t[2*v+1]);
  61. }
  62.  
  63. int main() {
  64.     int n=0;  cin >> n;
  65.  
  66.     for (int i=0; i<n; i++)
  67.         cin >> a[i];
  68.  
  69.     build(1, 0, n-1);
  70.  
  71.     int m=0; cin >> m;
  72.  
  73.     vector<long long> ans;
  74.  
  75.     for (int i=0; i<m; i++) {
  76.         char ch; cin >> ch;
  77.         if (ch == 'm') {
  78.             int l=0, r=0; cin >> l >> r;
  79.             ans.push_back(get(1, 0, n-1, l-1, r-1));
  80.         } else {
  81.             int l=0, r=0, x=0; cin >> l >> r >> x;
  82.             update(1, 0, n-1, l-1, r-1, x);
  83.         }
  84.     }
  85.     for (long long i: ans)
  86.         cout << i << ' ';
  87. }
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