Submission #868529

#	Time	Username	Problem	Language	Result	Execution time	Memory
868529		amirhoseinfar1385	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	198 ms	13696 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
long long n,m,s,t;
int kaf=(1<<18);

struct segment{
	long long seg[(1<<19)];
	void upd(int i,int l,int r,int tl,int tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]+=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
	long long pors(int i){
		if(i==0){
			return 0;
		}
		long long ret=seg[i]+pors((i>>1));
		return ret;
	}
}seg;

long long cal(int ind){
	if(ind==n){
		return 0;
	}
	long long av=seg.pors(kaf+ind);
	long long dov=seg.pors(kaf+ind+1);
	long long ret=0;
	if(dov>av){
		ret=-1ll*(dov-av)*s;
	}
	else{
		ret=1ll*(av-dov)*t;
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=0;i<=n;i++){
		int d;
		cin>>d;
		seg.upd(1,0,kaf-1,i,i,d);
	}
	long long res=0;
	for(int i=0;i<n;i++){
		res+=cal(i);
	}
	//cout<<res<<"\n";
	for(int i=0;i<m;i++){
		int l,r;
		long long w;
		cin>>l>>r>>w;
		res-=cal(l-1);
		res-=cal(r);
		seg.upd(1,0,kaf-1,l,r,w);
		res+=cal(l-1);
		res+=cal(r);
		cout<<res<<"\n";
	}
}

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