Submission #1001144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001144		vjudge3	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	494 ms	24148 KiB

foehn_phenomena

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

ll a[200005], s, t;
int n;

struct Node {
	ll x, lz;
} seg[800005];

void build (int id, int l, int r) {
	if (l == r) {
		seg[id].x = a[l];
		return;
	}
	build(id*2, l, (l+r)/2);
	build(id*2+1, (l+r)/2+1, r);
}

void push (int id) {
	seg[id].x += seg[id].lz;
	if (id <= n*2) {
		seg[id*2].lz += seg[id].lz;
		seg[id*2+1].lz += seg[id].lz;
	}
	seg[id].lz = 0;
}

void upd (int id, int l, int r, int ql, int qr, ll val) {
	push(id);
	if (qr < l || r < ql) return;
	if (ql <= l && r <= qr) {
		seg[id].lz += val;
		push(id);
		return;
	}
	upd(id*2, l, (l+r)/2, ql, qr, val);
	upd(id*2+1, (l+r)/2+1, r, ql, qr, val);
}

ll query (int id, int l, int r, int idx) {
	push(id);
	if (l == r) return seg[id].x;
	int mid = (l+r)/2;
	if (mid < idx) return query(id*2+1, mid+1, r, idx);
	return query(id*2, l, mid, idx);
}

ll upd (int idx) {
	ll cur = query(1, 1, n, idx);
	ll prv = idx == 1 ? 0 : query(1, 1, n, idx-1);
	ll nxt = idx == n ? cur : query(1, 1, n, idx+1);
	ll res = 0;
	if (prv < cur) res -= (cur - prv) * s;
	else res += (prv - cur) * t;
	if (cur < nxt) res -= (nxt - cur) * s;
	else res += (cur - nxt) * t;
	return res;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> n >> q >> s >> t >> a[0];
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i-1] < a[i]) ans -= (a[i] - a[i-1]) * s;
		else ans += (a[i-1] - a[i]) * t;
	}
	build(1, 1, n);
	while (q--) {
		int l, r;
		ll x;
		cin >> l >> r >> x;
		ans -= upd(l) + (l == r ? 0 : upd(r));
		upd(1, 1, n, l, r, x);
		ans += upd(l) + (l == r ? 0 : upd(r));
		cout << ans << '\n';
	}
	return 0;
}

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