Submission #209145

#	Time	Username	Problem	Language	Result	Execution time	Memory
209145		kai824	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	196 ms	7348 KiB

foehn_phenomena

#include "bits/stdc++.h"
using namespace std;

typedef pair<int,int> pii;
#define eb emplace_back
#define int int64_t

int arr[200005],ft2[200005],cost[200005],n;

inline int ls(int x){return x&(-x);}

void update2(int p,int v){
	for(p++;p<=n+3;p+=ls(p))ft2[p]+=v;
}
int query2(int p){
	int ans=0;
	for(p++;p;p-=ls(p))ans+=ft2[p];
	return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
		int q,s,t,c,l,r,u,sum=0;
		cin>>n>>q>>s>>t;
		for(int x=0;x<=n;x++)cin>>arr[x];
		for(int x=1;x<=n;x++){
			if(arr[x-1]<=arr[x])c=(arr[x]-arr[x-1])*(-s);
			else c=(arr[x-1]-arr[x])*t;
			sum+=c;
			update2(x,arr[x]);
			update2(x+1,-arr[x]);
		}
		while(q--){
			cin>>l>>r>>u;
			if(l>0){
				c=query2(l)-query2(l-1);
				if(c>=0)sum-=(-s)*(c);
				else sum-=t*abs(c);
			}
			if(r<n){
				c=query2(r+1)-query2(r);
				if(c>=0)sum-=(-s)*(c);
				else sum-=t*abs(c);
			}

			update2(l,u);update2(++r,-u);

			if(l>0){
				c=query2(l)-query2(l-1);
				if(c>=0)sum+=(-s)*(c);
				else sum+=t*abs(c);
			}
			if(r<=n){
				c=query2(r)-query2(r-1);
				if(c>=0)sum+=(-s)*(c);
				else sum+=t*abs(c);
			}
			cout<<sum<<'\n';
		}
    return 0;
}

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