Submission #1028087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028087		vjudge1	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	220 ms	13384 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << endl
#define all(x) x.begin(),x.end()

int a[200010];
ll tree[800010];

void propagate(int idx,int l,int r)
{
	if(l!=r && tree[idx]!=0)
	{
		tree[idx*2]+=tree[idx];
		tree[idx*2+1]+=tree[idx];
		tree[idx]=0;
	}
}

void build(int idx,int l,int r)
{
	if(l==r)
	{
		tree[idx]=a[l];
		return;
	}

	int mid=(l+r)/2;
	build(idx*2,l,mid);
	build(idx*2+1,mid+1,r);
}

void update(int idx,int l,int r,int x,int y,int v)
{
	if(r<x || y<l) return;
	propagate(idx,l,r);
	if(x<=l && r<=y)
	{
		if(l==r) tree[idx]+=v;
		else tree[idx]=v;
		propagate(idx,l,r);
		return;
	}

	int mid=(l+r)/2;
	update(idx*2,l,mid,x,y,v);
	update(idx*2+1,mid+1,r,x,y,v);
}

ll query(int idx,int l,int r,int x)
{
	if(l==r) return tree[idx];
	propagate(idx,l,r);

	int mid=(l+r)/2;
	if(x<=mid) return query(idx*2,l,mid,x);
	else return query(idx*2+1,mid+1,r,x);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,q,s,t;cin>>n>>q>>s>>t;
	for(int i=0;i<=n;i++) cin>>a[i];
	ll ans=0;
	for(int i=1;i<=n;i++) 
	{
		if(a[i-1]<a[i]) ans-=s*(a[i]-a[i-1]);
		else ans+=t*(a[i-1]-a[i]);
	}
	build(1,1,n);
	while(q--)
	{
		int l,r,x;cin>>l>>r>>x;
		ll v[4];
		if(l==1) v[0]=0;
		else v[0]=query(1,1,n,l-1);
		v[1]=query(1,1,n,l);
		v[2]=query(1,1,n,r);
		if(r==n) v[3]=v[2];
		else v[3]=query(1,1,n,r+1);

		if(v[0]<v[1]) ans+=s*(v[1]-v[0]);
		else ans-=t*(v[0]-v[1]);
		if(v[2]<v[3]) ans+=s*(v[3]-v[2]);
		else ans-=t*(v[2]-v[3]);

		v[1]+=x;
		v[2]+=x;
		if(r==n) v[3]=v[2];

		if(v[0]<v[1]) ans-=s*(v[1]-v[0]);
		else ans+=t*(v[0]-v[1]);
		if(v[2]<v[3]) ans-=s*(v[3]-v[2]);
		else ans+=t*(v[2]-v[3]);

		update(1,1,n,l,r,x);
		cout<<ans<<'\n';
	}
	// debug(ans);
	return 0;
}

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