제출 #948046

#제출 시각아이디문제언어결과실행 시간메모리
9480464QT0RFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
123 ms13648 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll base = 1<<18; ll tree[2*base]; void zmien(ll a, ll b, ll v){ a+=base-1; b+=base+1; while(a/2!=b/2){ if (!(a&1))tree[a+1]+=v; if (b&1)tree[b-1]+=v; a>>=1; b>>=1; } } ll sprawdz(ll v){ v+=base; ll ans=0; while(v){ ans+=tree[v]; v>>=1; } return ans; } ll cur=0,n,q,s,t; void change_wind(ll v, ll diff){ if (v==n+1)return; ll h1=sprawdz(v-1),h2=sprawdz(v); if (h1<h2)cur+=(h2-h1)*s; else cur+=(h2-h1)*t; if (h1<h2+diff)cur-=(h2+diff-h1)*s; else cur-=(h2+diff-h1)*t; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll a,b,c; cin >> n >> q >> s >> t; for (ll i = 0; i<=n; i++){ cin >> tree[base+i]; } for (ll i = 1; i<=n; i++){ if ((tree[base+i]>tree[base+i-1]))cur-=(tree[base+i]-tree[base+i-1])*s; else cur-=(tree[base+i]-tree[base+i-1])*t; } for (ll i = 1; i<=q; i++){ cin >> a >> b >> c; change_wind(a,c); change_wind(b+1,-c); zmien(a,b,c); cout << cur << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...