Submission #1199428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199428		Saul0906	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	272 ms	24692 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repr(a,b,c) for(int a=b-1; a>c-1; a--)
#define repa(a,b) for(auto a:b)
#define mid ((l+r)>>1)
#define endl "\n"

using namespace std;

const int N=2e5+5;

ll a[N];

struct segtree{
	segtree *left, *right;
	int l, r;
	ll v;
	segtree(int x, int y): l(x), r(y){
		v=a[l];
		if(l==r) return;
		v=0;
		left = new segtree(l,mid);
		right = new segtree(mid+1,r);
	}
	void update(int x, int y, ll z){
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			v+=z;
			return;
		}
		left->update(x,y,z);
		right->update(x,y,z);
	}
	ll query(int x){
		if(x<l || r<x) return 0;
		if(x<=l && r<=x) return v;
		return left->query(x)+right->query(x)+v;
	}
};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n, q, s, t, ans=0;
	cin>>n>>q>>s>>t;
	s*=-1;
	rep(i,0,n+1) cin>>a[i];
	rep(i,1,n+1){
		if(a[i]>a[i-1]) ans+=s*(a[i]-a[i-1]);
		else ans+=t*(a[i-1]-a[i]);
	}
	ll l, r, x;
	segtree st(0,n);
	while(q--){
		cin>>l>>r>>x;
		ll a, b, c, d;
		a=st.query(l-1);
		b=st.query(l);
		c=st.query(r);
		d=st.query(r+1);
		st.update(l,r,x);
		if(b>a) ans-=s*(b-a);
		else ans-=t*(a-b);
		b+=x;
		if(b>a) ans+=s*(b-a);
		else ans+=t*(a-b);
		if(r<n){
			if(d>c) ans-=s*(d-c);
			else ans-=t*(c-d);
			c+=x;
			if(d>c) ans+=s*(d-c);
			else ans+=t*(c-d);
		}
		cout<<ans<<endl;
	}
}

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