Submission #129526

#TimeUsernameProblemLanguageResultExecution timeMemory
129526khanhFoehn Phenomena (JOI17_foehn_phenomena)C++11
0 / 100
1079 ms14212 KiB
#include<bits/stdc++.h> #define inf 1e15 + 7 #define N 200005 #define ll long long using namespace std; ll n,q,up,down; ll arr[N] , lazy[N<<2] , node[N<<2]; ll ans = 0; void build_tree(ll i,ll l,ll r) { if(l>r) return; if(l==r) { node[i] = arr[l]; return; } ll m = (l + r) / 2; build_tree(i<<1 , l , m); m++; build_tree(i<<1|1 , m , r); } void true_val(ll i,ll l,ll r) { if(l!=r) { node[i<<1] += lazy[i]; lazy[i<<1] += lazy[i]; node[i<<1|1] += lazy[i]; lazy[i<<1|1] += lazy[i]; lazy[i] = 0; } } void update(ll i,ll l,ll r,ll a,ll b,ll val) { if(l>r || b<l || r<a) return; if(a<=l && r<=b) { node[i] += val; lazy[i] += val; return; } true_val(i,l,r); ll m = (l + r) / 2; update(i<<1 , l , m , a , b , val); m++; update(i<<1|1 , m , r , a , b , val); node[i] = max(node[i<<1],node[i<<1|1]); } ll get_max(ll i,ll l,ll r,ll a,ll b) { true_val(i,l,r); if(l>r || b<l || r<a) return -inf; if(a<=l && r<=b) return node[i]; ll m = (l + r) / 2; return max(get_max(i<<1,l,m,a,b),get_max(i<<1|1,m+1,r,a,b)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q>>down>>up; memset(lazy,0,sizeof(lazy)); for(ll i=0;i<=n;i++) cin>>arr[i]; build_tree(1,1,n); for(ll i=0;i<=n-1;i++) { if(arr[i] < arr[i+1]) ans -= down * abs(arr[i] - arr[i+1]); else ans += up * abs(arr[i] - arr[i+1]); } while(q--) { ll l,r,x; cin>>l>>r>>x; ll MAX1 = (l==1 ? 0 : get_max(1,1,n,l-1,l-1)); ll MAX2 = get_max(1,1,n,l,l); if(MAX1 < MAX2 && MAX1 >= MAX2 + x) { ans += down * abs(MAX1 - MAX2); ans += up * abs(MAX1 - MAX2 - x); } if(MAX1 < MAX2 && MAX1 < MAX2 + x) { ans += down * abs(MAX1 - MAX2); ans -= down * abs(MAX1 - MAX2 - x); } if(MAX1 >= MAX2 && MAX1 < MAX2 + x) { ans -= down * abs(MAX1 - MAX2 - x); ans -= up * abs(MAX1 - MAX2); } if(MAX1 >= MAX2 && MAX1 >= MAX2 + x) { ans -= up * abs(MAX1 - MAX2); ans += up * abs(MAX1 - MAX2 - x); } if(r <= n - 1) { ll MAX3 = get_max(1 , 1 , n , r , r); ll MAX4 = get_max(1 , 1 , n , r + 1 , r + 1); if(MAX3 < MAX4 && MAX3 + x >= MAX4) { ans += down * abs(MAX3 - MAX4); ans += up * abs(MAX3 + x - MAX4); } if(MAX3 < MAX4 && MAX3 + x < MAX4) { ans += down * abs(MAX3 - MAX4); ans -= down * abs(MAX3 + x - MAX4); } if(MAX3 >= MAX4 && MAX3 + x < MAX4) { ans -= up * abs(MAX3 - MAX4); ans -= down * (MAX3 + x - MAX4); } if(MAX3 >= MAX4 && MAX3 + x >= MAX4) { ans -= up * abs(MAX3 - MAX4); ans += up * abs(MAX3 + x - MAX4); } } cout<<ans<<endl; update(1,1,n,l,r,x); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...