Submission #1126942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126942		heey	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	268 ms	9904 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5+2;
int n, q, s, t;
long long a[maxn];
long long lazy[4*maxn];

void build(int v, int l, int r){
	if(l == r){
		lazy[v] = a[l];
		return;
	}
	int m = (l+r)>>1;
	build(v<<1, l, m);
	build(v<<1|1, m+1, r);

}

void update(int l, int r, int val, int v, int tl, int tr){
	if(tl > r || tr < l || tl > tr) return;

	if(tl >= l && tr <= r) {
		lazy[v] += val;
		return;
	}
	int m = (tl+tr)>>1;
	update(l, r, val, v<<1, tl, m);
	update(l, r, val, v<<1|1, m+1, tr);
}



int get(int pos, int v, int l, int r){
	if(l == r) return lazy[v];

	int m = (l+r)>>1;
	if(pos <= m) return lazy[v] + get(pos, v<<1, l, m);
	else return lazy[v] + get(pos, v<<1|1, m+1, r);
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q >> s >> t;
	for(int i = 0; i <= n; i++) cin >> a[i];

	int ans = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] > a[i-1]) ans -= (long long)s * (a[i] - a[i-1]);
			else ans += (long long)t * (a[i-1] - a[i]);
	}

	build(1, 0, n);
	
	while(q--){
		int l, r, x; cin >> l >> r >> x;

		if(l != 0) {
			int la = get(l-1, 1, 0, n);
			int lb = get(l, 1, 0, n);
			if(lb > la) ans += (long long)s * (lb - la);
			else ans -= (long long)t * (la - lb);
		}
		if(r != n){
			int ra = get(r, 1, 0, n);
			int rb = get(r+1, 1, 0, n);
			if(rb > ra) ans += (long long)s * (rb - ra);
			else ans -= (long long)t * (ra - rb);
		}

		update(l, r, x, 1, 0, n);

		if(l != 0) {
			int la = get(l-1, 1, 0, n);
			int lb = get(l, 1, 0, n);
			if(lb > la) ans -= (long long)s * (lb - la);
			else ans += (long long)t * (la - lb);
		}
		if(r != n){
			int ra = get(r, 1, 0, n);
			int rb = get(r+1, 1, 0, n);
			if(rb > ra) ans -= (long long)s * (rb - ra);
			else ans += (long long)t * (ra - rb);
		}

		cout << ans << '\n';
	}
	return 0;
}

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