Submission #129288

#	Time	Username	Problem	Language	Result	Execution time	Memory
129288		nhimnam120	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	10 / 100	846 ms	11468 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
const long long N=2e5+5;
long long alt[N];
long long diff[N];
long long node[N*4];
long long n,q,s,t;
void build_tree(long long id, long long l, long long r){
	if(l>r){
		return;
	}
	if(l==r){
		//cout << diff[l]<< " ";
		node[id] = diff[l];
		return;
	}
	long long mid = (l+r)/2;
	build_tree(id*2,l,mid);
	build_tree(id*2+1,mid+1,r);
	node[id]=0;
	if(mid-l==0){
		if(node[id*2]>0){
			node[id] = node[id] - node[id*2]*s;
		}
		else{
			node[id] = node[id] - node[id*2]*t;
		}
	}
	else{
		node[id]+=node[id*2];
	}
	if(r-mid-1==0){
		if(node[id*2+1]>0){
			node[id] = node[id] - node[id*2+1]*s;
		}
		else{
			node[id] = node[id] - node[id*2+1]*t;
		}
	}
	else{
		node[id]+=node[id*2+1];
	}
}
void update(long long id, long long l, long long r, long long pos, long long val){
	if(r<pos||l>pos||l>r){
		return;
	}
	if(l==r){
		node[id] = node[id] + val;
		return;
	}
	long long mid = (l+r)/2;
	update(id*2,l,mid,pos,val);
	update(id*2+1,mid+1,r,pos,val);
	node[id]=0;
	if(mid-l==0){
		if(node[id*2]>0){
			node[id] = node[id] - node[id*2]*s;
		}
		else{
			node[id] = node[id] - node[id*2]*t;
		}
	}
	else{
		node[id]+=node[id*2];
	}
	if(r-mid-1==0){
		if(node[id*2+1]>0){
			node[id] = node[id] - node[id*2+1]*s;
		}
		else{
			node[id] = node[id] - node[id*2+1]*t;
		}
	}
	else{
		node[id]+=node[id*2+1];
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> s >> t;
	for(int i=0;i<=n;i++){
		cin >> alt[i];
		if(i>=1){
			diff[i] = alt[i] - alt[i-1];
		}
	}
	build_tree(1,1,n);
	while(q--){
		long long l, r, x;
		cin >> l >> r >> x;
		update(1,1,n,l,x);
		update(1,1,n,r+1,-x);
		cout << node[1]<<endl;
	}
}

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