Submission #966545

#	Time	Username	Problem	Language	Result	Execution time	Memory
966545		yellowtoad	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	697 ms	17532 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;

long long n, q, s, t, a[200010], node[1000010], l, r, val, tmpl, tmpr, tnpl, tnpr, ans, tmp, tnp;

void update(int id, int x, int y) {
	if ((r < x) || (y < l)) return;
	if ((l <= x) && (y <= r)) {
		node[id] += val;
		return;
	}
	int mid = (x+y)/2;
	update(id*2,x,mid);
	update(id*2+1,mid+1,y);
}

long long find(int id, int x, int y, int pos) {
	if (x == y) return a[x]+node[id];
	int mid = (x+y)/2;
	node[id*2] += node[id];
	node[id*2+1] += node[id];
	node[id] = 0;
	if (pos <= mid) return find(id*2,x,mid,pos);
	else return find(id*2+1,mid+1,y,pos);
}

int main() {
	cin >> n >> q >> s >> t;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
		if (i > 0) {
			if (a[i] > a[i-1]) ans += s*(a[i-1]-a[i]);
			else ans += t*(a[i-1]-a[i]);
		}
	}
	while (q--) {
		cin >> l >> r >> val;
		if (r == n) tmpr = 0;
		else {
			tmp = find(1,0,n,r);
			tnp = find(1,0,n,r+1);
			if (tmp > tnp) tmpr = (tmp-tnp)*t;
			else tmpr = (tmp-tnp)*s;
		}
		tmp = find(1,0,n,l);
		tnp = find(1,0,n,l-1);
		if (tmp > tnp) tmpl = (tnp-tmp)*s;
		else tmpl = (tnp-tmp)*t;
		update(1,0,n);
		if (r == n) tnpr = 0;
		else {
			tmp = find(1,0,n,r);
			tnp = find(1,0,n,r+1);
			if (tmp > tnp) tnpr = (tmp-tnp)*t;
			else tnpr = (tmp-tnp)*s;
		}
		tmp = find(1,0,n,l);
		tnp = find(1,0,n,l-1);
		if (tmp > tnp) tnpl = (tnp-tmp)*s;
		else tnpl = (tnp-tmp)*t;
		ans += (tnpl-tmpl)+(tnpr-tmpr);
		cout << ans << endl;
	}
}

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