Submission #129291

#	Time	Username	Problem	Language	Result	Execution time	Memory
129291		ntrung03	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	597 ms	13944 KiB

foehn_phenomena

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> a;
int st[800002];
int lazy[800002];
void build(int node, int start, int end){
	if(start==end){
		st[node] = a[start];
		return;
	}
	int mid = (start+end)/2;
	build(2*node,start,mid);
	build(2*node+1,mid+1,end);
	st[node] = st[2*node]+st[2*node+1];
	return;
}
void update(int node, int start, int end,int l, int r, int val){
	if(lazy[node]){
		st[node]+= (end-start+1)*lazy[node];
		if(start!=end){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node] =0;
	}
	if(r<start||l>end||l>r)
		return;
	if(l==start&&r==end){
		st[node]+=(end-start+1)*val;
		if(start!=end){
			lazy[2*node]+=val;
			lazy[2*node+1]+=val;
		}
		return;
	}
	int mid = (start+end)/2;
	update(2*node, start, mid, l, min(mid,r), val);
	update(2*node+1, mid+1, end, max(mid+1,l), r, val);
	st[node] = st[2*node]+st[2*node+1];
}
int query(int node, int start, int end, int l, int r){
	
	if(r<start||l>end||l>r)
	return 0;
	if(lazy[node]){
		st[node]+=(end-start+1)*lazy[node];
		if(start!=end){
			lazy[2*node]+=lazy[node];
			lazy[2*node+1]+=lazy[node];
		}
		lazy[node] =0;
	}
	if(l==start&&r==end){
		return st[node];
	}
	int mid = (start+end)/2;
	int p1 = query(2*node,start,mid,l,min(mid,r));
	int p2 = query(2*node+1,mid+1,end,max(mid+1,l),r);
	return p1+p2;
}
signed main() {
  	ios::sync_with_stdio(false);
  	cin.tie(0);
	int n,q,s,t;
	cin>>n>>q>>s>>t;
	a.resize(n+1);
	for(int i=0;i<=n;i++) cin>>a[i];
	int res = 0;
	for(int i=0;i<n;i++)
	if(a[i]<a[i+1]) res-=s*(a[i+1]-a[i]);
	else res+=t*(a[i]-a[i+1]);
	build(1, 0, n);
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
//		l--;
//		r--;
		if(l>0){
			int pl = query(1,0,n,l-1,l-1);
			int ll = query(1, 0, n, l, l);
			if(pl<ll) res= res+s*(ll-pl);
			else if(pl>=ll) res = res-t*(pl-ll);
			ll+=x;
			if(pl<ll) res-=s*(ll-pl);
			else res+=t*(pl-ll);
		}
		if(r<n)
		{
			int rr = query(1, 0, n, r, r);
			int ar = query(1, 0, n, r+1, r+1);
			if(rr<ar) res+=s*(ar-rr);
			else res-=t*(rr-ar);
			rr+=x;
			if(rr<ar) res-=s*(ar-rr);
			else res+=t*(rr-ar);
		}
		update(1, 0, n, l, r, x);
		cout<<res<<'\n';
	}
}

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