Submission #964512

#	Time	Username	Problem	Language	Result	Execution time	Memory
964512		PM1	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	265 ms	15588 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=2e5+5,tt=19;
ll n,q,s,t,ans=0,a[mxn];
struct segment{
	ll val[(1<<tt)];
	void add(int id,int L,int R,int l,int r,ll x){
		if(L==l && R==r){
			val[id]+=x;
			return;
		}
		int mid=(L+R)/2;
		if(l<mid)
			add(id*2,L,mid,l,min(r,mid),x);
		if(r>mid)
			add(id*2+1,mid,R,max(l,mid),r,x);
	}
	ll get(int id,int L,int R,int x){
		if(L+1==R)
			return val[id];
		int mid=(L+R)/2;
		if(x<mid)
			return get(id*2,L,mid,x)+val[id];
		else
			return get(id*2+1,mid,R,x)+val[id];
	}
}seg;
ll f(ll x,ll y){
	if(x>=y)
		return (x-y)*t;
	return (x-y)*s;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>s>>t;
	for(int i=0;i<=n;i++){
		cin>>a[i];
		seg.add(1,0,n+1,i,i+1,a[i]);
	}
	for(int i=1;i<=n;i++){
		ans+=f(a[i-1],a[i]);
	}
	while(q--){
		ll l,r,x,w,z,ww,zz;
		cin>>l>>r>>x;
		if(l!=0){
			w=seg.get(1,0,n+1,l-1);
			z=seg.get(1,0,n+1,l);
			ans-=f(w,z);
			ans+=f(w,z+x);
		}
		if(r!=n){
			ww=seg.get(1,0,n+1,r);
			zz=seg.get(1,0,n+1,r+1);
			ans-=f(ww,zz);
			ans+=f(ww+x,zz);
		}
		
		seg.add(1,0,n+1,l,r+1,x);
		cout<<ans<<'\n';
	}
	return 0;
}

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