Submission #737672

#	Time	Username	Problem	Language	Result	Execution time	Memory
737672		1075508020060209tc	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	605 ms	13072 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define int long long
int lowbit(int x){return x&-x;}
int n;int ar[500005];int Q;int S;int T;

int solve(){

int ans=0;
for(int i=1;i<=n;i++){
    if(ar[i]>ar[i-1]){
        ans-=S*(ar[i]-ar[i-1]);
    }else{
        ans+=T*(ar[i-1]-ar[i]);
    }
}
return ans;
}

int bit[500005];

void upd(int pl,int vl){
while(pl){
    bit[pl]+=vl;
    pl-=lowbit(pl);
}
}
int qsum(int pl){
if(pl==0){return 0;}

int ret=0;
while(pl<=500000){
    ret+=bit[pl];
    pl+=lowbit(pl);
}
return ret;
}





signed main(){
cin>>n>>Q>>S>>T;
for(int i=0;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=n;i++){
    upd(i,ar[i]);
    upd(i-1,-ar[i]);
}
int ans=solve();



while(Q--){
    int l;int r;int v;
    cin>>l>>r>>v;
    int a;int b;
    a=qsum(l-1);b=qsum(l);
    if(a<b){
        ans+=S*abs(a-b);
    }else{
        ans-=T*abs(a-b);
    }
    a=qsum(r);b=qsum(min(n,r+1));
    if(a<b){
        ans+=S*abs(a-b);
    }else{
        ans-=T*abs(a-b);
    }

    upd(r,v);
    upd(l-1,-v);

    a=qsum(l-1);b=qsum(l);
    if(a<b){
        ans-=S*abs(a-b);
    }else{
        ans+=T*abs(a-b);
    }
    a=qsum(r);b=qsum(min(n,r+1));
    if(a<b){
        ans-=S*abs(a-b);
    }else{
        ans+=T*abs(a-b);
    }

    cout<<ans<<endl;




}



}

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