fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
  4. #define ll long long
  5. #define pb push_back
  6. #define all(x) x.begin(), x.end()
  7.  
  8. const ll INF = 1e18;
  9. const int N = 1e5+5;
  10.  
  11. struct node{
  12.     ll val, lazy;
  13. } seg[4*N];
  14. int n, m;
  15.  
  16. void down(int id){
  17.     ll k = seg[id].lazy;
  18.     if (k!=0){
  19.         seg[2*id].val += k;
  20.         seg[2*id].lazy += k;
  21.  
  22.         seg[2*id+1].val += k;
  23.         seg[2*id+1].lazy += k;
  24.  
  25.         seg[id].lazy = 0;
  26.     }
  27. }
  28.  
  29. void update(int id, int l, int r, int u, int v, int k){
  30.     if (l>v || r<u) return;
  31.     if (u<=l && r<=v){
  32.         seg[id].val += k;
  33.         seg[id].lazy += k;
  34.         return;
  35.     }
  36.     down(id);
  37.     int m = (l+r)/2;
  38.     update(2*id, l, m, u, v, k);
  39.     update(2*id+1, m+1, r, u, v, k);
  40.     seg[id].val = max(seg[2*id].val, seg[2*id+1].val);
  41. }
  42.  
  43. ll get(int id, int l, int r, int u, int v){
  44.     if (l>v || r<u){
  45.         return -INF;
  46.     }
  47.     if (u<=l && r<=v){
  48.         return seg[id].val;
  49.     }
  50.     down(id);
  51.     int m = (l+r)/2;
  52.     ll get1 = get(2*id, l, m, u, v);
  53.     ll get2 = get(2*id+1, m+1, r, u, v);
  54.     return max(get1, get2);
  55. }
  56.  
  57. int main(){
  58.     fastIO;
  59.  
  60.     cin >> n >> m;
  61.     while (m--){
  62.         int type;
  63.         cin >> type;
  64.         if (type==0){
  65.             int u, v, k;
  66.             cin >> u >> v >> k;
  67.             update(1, 1, n, u, v, k);
  68.         }
  69.         else{
  70.             int u, v;
  71.             cin >> u >> v;
  72.             cout << get(1, 1, n, u, v) << '\n';
  73.         }
  74.     }
  75. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JQ4gQe
language:
C++14 (gcc 8.3)
created:
2 days 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!