Submission #852659

#	Time	Username	Problem	Language	Result	Execution time	Memory
852659		stdfloat	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	503 ms	23488 KiB

foehn_phenomena

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

using ll = long long;

vector<int> a;

vector<ll> st, lz;

ll bld(int nd, int l, int r) {
	if (l == r) {
		return st[nd] = a[l];
	}

	int ch = nd<<1, md = (l + r)>>1;
	return st[nd] = bld(ch, l, md) + bld(ch + 1, md + 1, r);
}

void LZ(int nd, int l, int r) {
	st[nd] += (r - l + 1) * lz[nd];
	if (l != r) {
		int ch = nd<<1;
		lz[ch] += lz[nd];
		lz[ch + 1] += lz[nd];
	}
	lz[nd] = 0;
}

void upd(int nd, int l, int r, int x, int y, int val) {
	LZ(nd, l, r);
	if (r < x || y < l) return;

	if (x <= l && r <= y) {
		lz[nd] += val;
	}
	else {
		int ch = nd<<1, md = (l + r)>>1;
		upd(ch, l, md, x, y, val);
		upd(ch + 1, md + 1, r, x, y, val);
	}
}

ll fnd(int nd, int l, int r, int x) {
	LZ(nd, l, r);
	if (l > x || x > r) return 0;

	if (l == r) return st[nd];

	int ch = nd<<1, md = (l + r)>>1;
	return fnd(ch, l, md, x) + fnd(ch + 1, md + 1, r, x);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, q, s, t;
	cin >> n >> q >> s >> t;

	a.assign(n + 1, 0);
	st.assign((n<<2) + 5, 0);
	lz.assign((n<<2) + 5, 0);
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		cin >> a[i];
		if (i) ans += 1LL * (a[i - 1] < a[i] ? s : t) * (a[i - 1] - a[i]);
	}

	bld(1, 0, n);

	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;

		if (l) {
			ll y = fnd(1, 0, n, l - 1), z = fnd(1, 0, n, l);
			ans -= 1LL * (y < z ? s : t) * (y - z);
		}
		if (r != n) {
			ll y = fnd(1, 0, n, r), z = fnd(1, 0, n, r + 1);
			ans -= 1LL * (y < z ? s : t) * (y - z);
		}

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

		if (l) {
			ll y = fnd(1, 0, n, l - 1), z = fnd(1, 0, n, l);
			ans += 1LL * (y < z ? s : t) * (y - z);
		}
		if (r != n) {
			ll y = fnd(1, 0, n, r), z = fnd(1, 0, n, r + 1);
			ans += 1LL * (y < z ? s : t) * (y - z);
		}

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

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