fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define pii pair<int,int>
  5. #define pll pair<ll,ll>
  6. #define plll pair<ll,pll>
  7. #define tull tuple<ll,ll,ll>
  8. #define pb push_back
  9. #define f first
  10. #define endl "\n"
  11. #define se second
  12. #define piii pair<int,pii>
  13. #define id1 id<<1
  14. #define id2 (id<<1)+1
  15. #define MASK(i) (1<<i)
  16. #define TIME "\nTime elapsed : "<<(double)clock()/1000<<" ms"
  17. #define all(x) x.begin(),x.end()
  18. #define TASK "test"
  19. #define fast ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
  20. using namespace std;
  21. const ll mod = 1e9 + 7;
  22. const ll INF = 1e16;
  23. const ll maxn = 5e5 + 5;
  24. const ll maxs = 1e7;
  25. const ll dx[] = { -1, 0, 0, 1 };
  26. const ll dy[] = { 0, -1, 1, 0 };
  27.  
  28. ll n,q;
  29. ll a[maxn];
  30. ll lazy[4 * maxn + 5];
  31. ll st[4 * maxn + 5];
  32.  
  33. void build(ll id,ll l,ll r)
  34. {
  35.     if(l == r){
  36.         st[id] = a[l];
  37.         return;
  38.     }
  39.  
  40.     ll mid = (l + r) >> 1;
  41.     build(id * 2,l,mid);
  42.     build(id * 2 + 1,mid + 1,r);
  43.  
  44.     st[id] = max(st[id * 2],st[id * 2 + 1]);
  45. }
  46.  
  47. void down(ll id,ll l,ll r)
  48. {
  49.     ll mid = (l + r) >> 1;
  50.     st[id * 2] += lazy[id];
  51.     lazy[id * 2] += lazy[id];
  52.     st[id * 2 + 1] += lazy[id];
  53.     lazy[id * 2 + 1] += lazy[id];
  54.     lazy[id] = 0;
  55. }
  56.  
  57. void update(ll id,ll l,ll r,ll u,ll v,ll val)
  58. {
  59.     if(v < l || r < u){
  60.         return;
  61.     }
  62.  
  63.     if(u <= l && r <= v){
  64.         st[id] += val;
  65.         lazy[id] += val;
  66.         return;
  67.     }
  68.  
  69.     down(id,l,r);
  70.  
  71.     ll mid = (l + r) >> 1;
  72.     update(id * 2,l,mid,u,v,val);
  73.     update(id * 2 + 1,mid + 1,r,u,v,val);
  74.  
  75.     st[id] = max(st[id * 2],st[id * 2 + 1]);
  76. }
  77.  
  78. ll get(ll id,ll l,ll r,ll u,ll v)
  79. {
  80.     if(v < l || r < u){
  81.         return 0;
  82.     }
  83.  
  84.     if(u <= l && r <= v){
  85.         return st[id];
  86.     }
  87.  
  88.     down(id,l,r);
  89.     int mid = (l + r) >> 1;
  90.     return max(get(id * 2,l,mid,u,v),get(id * 2 + 1,mid + 1,r,u,v));
  91. }
  92.  
  93. int main()
  94. {
  95.     fast
  96.  
  97.     cin >> n >> q;
  98.  
  99.     for(int i = 1; i <= n; ++i){
  100.         cin >> a[i];
  101.     }
  102.  
  103.     build(1,1,n);
  104.  
  105.     while(q--){
  106.         int i;
  107.         cin >> i;
  108.         if(i == 1){
  109.             ll u,v,x;
  110.             cin >> u >> v >> x;
  111.             update(1,1,n,u,v,x);
  112.         }
  113.         else{
  114.             int u,v;
  115.             cin >> u >> v;
  116.             cout << get(1,1,n,u,v) << endl;
  117.         }
  118.     }
  119.  
  120.     return 0;
  121. }
  122.  
Runtime error #stdin #stdout 2.06s 2095568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bn9u6d
language:
C++14 (gcc 8.3)
created:
184 days ago
visibility:
secret

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!