Submission #860687

#	Time	Username	Problem	Language	Result	Execution time	Memory
860687		Iliya_	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	220 ms	17744 KiB

foehn_phenomena

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std;
typedef long long ll; 

const ll N = 2e5+7; 
ll a[N], seg[N<<2];

void build(ll ind, ll l, ll r){
     if (l == r){
          seg[ind] = a[l]; 
          return;
     }
     ll mid = (l+r)>>1; 
     build(2*ind,l,mid);
     build(2*ind+1,mid+1,r); 
}

void shift(ll ind, ll l, ll r){
     if (l == r) return; 
     seg[2*ind] += seg[ind]; 
     seg[2*ind+1] += seg[ind]; 
     seg[ind] = 0;
}

void upd(ll ind, ll l, ll r, ll st, ll en, ll val){
     shift(ind,l,r);
     if (l > en || st > r) return;
     if (l == r || (l >= st && r <= en)){
          seg[ind] += val;
          return;
     }
     ll mid = (l+r)>>1;
     upd(2*ind,l,mid,st,en,val);
     upd(2*ind+1,mid+1,r,st,en,val);
}

ll get(ll ind, ll l, ll r, ll id){
     shift(ind,l,r); 
     if (l == r) return seg[ind]; 
     ll mid = (l+r)>>1; 
     if (id <= mid) return get(2*ind,l,mid,id);
     else return get(2*ind+1,mid+1,r,id);
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

     ll n,q,s,t; cin >> n >> q >> s >> t; 
     for(ll i=0; i<=n; i++) cin >> a[i]; 
     build(1,0,n); 
     ll mos = 0, man = 0;
     for(ll i=1; i<=n; i++){
          if (a[i] > a[i-1]) man += (a[i] - a[i-1]); 
          else mos += (a[i-1] - a[i]); 
     }
     while(q--){
          ll l,r,x; cin >> l >> r >> x; 
          if (l > 0){
               ll a = get(1,0,n,l-1), b = get(1,0,n,l); 
               if (a < b) man -= (b-a); 
               else mos -= (a-b); 
               b += x; 
               if (a < b) man += (b-a);
               else mos += (a-b); 
          }
          if (r < n){
               ll a = get(1,0,n,r), b = get(1,0,n,r+1); 
               if (a < b) man -= (b-a); 
               else mos -= (a-b); 
               a += x; 
               if (a < b) man += (b-a);
               else mos += (a-b); 
          }
          upd(1,0,n,l,r,x); 
          ll ans = mos * t - man * s; 
          cout << ans << endl;
     }

     return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60