| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 29373 | 2017-07-19T07:47:56 Z | PrOAhMeT | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 39 ms | 7648 KB |
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXN=200015;
int n,q,a[MAXN];
LL fen[MAXN],s,tt;
struct fenwick_tree {
LL fen[MAXN];
void upd(int x,LL y) {
++x;
for(;x<MAXN;x+=x&-x)
fen[x]+=y;
}
LL get(int x) {
++x;
LL ret=0;
for(;x;x-=x&-x)
ret+=fen[x];
return ret;
}
} h,t;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q>>s>>tt;
LL temp=0;
for(int i=0;i<=n;++i) {
cin>>a[i];
if(i>0) {
if(a[i]>a[i-1]) {
t.upd(i,-s*(a[i]-a[i-1]));
}
else {
t.upd(i,tt*(a[i-1]-a[i]));
}
}
if(i) h.upd(i,a[i]-a[i-1]);
else h.upd(i,a[i]);
}
int l,r,x;
LL bef,cur,beft,curt,nw;
for(int i=0;i<q;++i) {
cin>>l>>r>>x;
LL oldl,oldr;
if(l>0)
oldl=t.get(l)-t.get(l-1);
if(r<n)
oldr=t.get(r+1)-t.get(r);
h.upd(l,x);
h.upd(r+1,-x);
if(l>0) {
bef=h.get(l-1);
cur=h.get(l);
if(bef>cur) {
t.upd(l,tt*(bef-cur)-oldl);
}
else t.upd(l,-s*(cur-bef)-oldl);
}
if(r<n) {
bef=h.get(r);
cur=h.get(r+1);
if(cur<bef) {
t.upd(r+1,tt*(bef-cur)-oldr);
}
else t.upd(r+1,-s*(cur-bef)-oldr);
}
//cout<<"update "<<i+1<<endl;
//for(int j=0;j<=n;++j)
//cout<<j<<" "<<t.get(j)<<" "<<h.get(j)<<endl;
cout<<t.get(n)<< endl;
}
}