fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll N = 4e5 + 5;
  5. ll n,q,t,w;
  6. ll a[N], b[N];
  7. bool check(ll val)
  8. {
  9.     ll l = 1, r = n;
  10.     for(int i = 1; i <= n; i++)
  11.     {
  12.         ll phu = a[i] - val;
  13.         if(phu <= 0) continue;
  14.         l = max(l, i - (w - phu));
  15.         r = min(r, i + (w - phu));
  16.     }
  17.     return (l<=r);
  18. }
  19. int main()
  20. {
  21.      ios_base::sync_with_stdio(0);
  22.      cout.tie(0);cin.tie(0);
  23.      cin >> n >> q >> t >> w;
  24.      for(int i = 1; i <= n; i++) cin >> a[i];
  25.  
  26.      for(int i=1;i<=q;i++){
  27.           int l, r, c;
  28.           cin >> l >> r >> c;
  29.           b[l] += c;
  30.           b[r + 1] -= c;
  31.      }
  32.      ll MAX = 0;
  33.      for(int i = 1; i <= n; i++){
  34.           b[i] = b[i - 1] + b[i];
  35.           a[i] = a[i] + b[i];
  36.           MAX = max(MAX, a[i]);
  37.      }
  38.      if(t==1)
  39.      {
  40.           long long l = -2e9, r = 2e9, mid, res;
  41.           while(l <= r){
  42.                mid = (l + r) / 2;
  43.                if(check(mid)){
  44.                     res = mid;
  45.                     r = mid - 1;
  46.                }
  47.                else l = mid + 1;
  48.           }
  49.           cout << res;
  50.      }
  51.      else cout << MAX;
  52. }
  53.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cCGeEH
language:
C++14 (clang 8.0)
created:
1 day 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!