Submission #1180122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180122		jbareja	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	100 ms	9908 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct SegTree {
	int n;
	int base;
	vector<ll> values;

	void Init(vector<ll>& vec) {
		n = vec.size();
		base = 1;
		while (base <= n) base *= 2;
		values.assign(base * 2, 0);
		for (int i=0; i<vec.size(); i++) values[base + i] = vec[i];
	}

	void Add(int l, int r, ll val) {
		l += base - 1;
		r += base + 1;
		while (l/2 != r/2) {
			if (l % 2 == 0) values[l+1] += val;
			if (r % 2 != 0) values[r-1] += val;
			l /= 2, r /= 2;
		}
	}

	ll Val(int x) {
		x += base;
		ll ans = 0;
		while (x) {
			ans += values[x];
			x /= 2;
		}
		return ans;
	}
};

int N; // N+1 - liczba miejsc o danych wysokościach
int Q; // liczba zapytań
ll S; // zmniejszenie temperatury na jednostkę wysokości, jeżeli wysokość się zwiększa
ll T; // zwiększenie temperatury na jednostkę wysokości, jeżeli wysokość się zmniejsza

vector<ll> A;
SegTree tree;

ll ans_before_changes() {
	ll temperature = 0;
	for (int i=1; i<=N; i++) {
		if (A[i] > A[i-1]) temperature -= abs(A[i] - A[i-1]) * S;
		else temperature += abs(A[i] - A[i-1]) * T;
	}
	return temperature;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> Q >> S >> T;

	A.assign(N+1, 0);
	for (int i=0; i<=N; i++) cin >> A[i];
	tree.Init(A);

	ll ans = ans_before_changes();

	for (int i=0; i<Q; i++) {
		int L, R; ll X;
		cin >> L >> R >> X;
		ll old_L = tree.Val(L); // wartość L przed zmianą
		ll old_R = tree.Val(R); // wartość R przed zmianą
		tree.Add(L, R, X);

		ll new_L = old_L + X; // wartość L po zmianie
		ll prev_L = tree.Val(L-1); // wartość elementu przed L

		ll old_delta_L = old_L - prev_L;
		ll new_delta_L = new_L - prev_L;

		if (old_delta_L > 0) ans -= -old_delta_L * S;
		else ans -= -old_delta_L * T;

		if (new_delta_L > 0) ans += -new_delta_L * S;
		else ans += -new_delta_L * T;

		if (R < N) {
			ll new_R = old_R + X; // wartość R po zmianie
			ll next_R = tree.Val(R+1); // wartość elementu po R

			ll old_delta_R = next_R - old_R;
			ll new_delta_R = next_R - new_R;

			if (old_delta_R > 0) ans -= -old_delta_R * S;
			else ans -= -old_delta_R * T;

			if (new_delta_R > 0) ans += -new_delta_R * S;
			else ans += -new_delta_R * T;
		}

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

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