제출 #1264454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264454		XXBabaProBerkay	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	106 ms	7240 KiB

foehn_phenomena

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

#define F first
#define S second
#define PB push_back
#define MP make_pair

const int INF = 1e9 + 7;
const int MOD = 998244353;

using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;

template<class T>
using vec = vector<T>;

ll N, Q, S, T;
vec<ll> t;

void update(int l, int r, int x)
{
	for (l += N - 1, r += N - 1; l <= r; l /= 2, r /= 2)
	{
		if (l % 2 == 1) t[l++] += x;
		if (r % 2 == 0) t[r--] += x;
	}
}

ll query(int p)
{
	if (p == 0) return 0;
	p = min(p, (int)N);

	ll ans = 0;
	for (p += N - 1; p > 0; p /= 2)
		ans += t[p];

	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Q >> S >> T;
	t.assign(N * 2, 0);
	ll ans = 0;
	for (int i = N - 1; i < N * 2; i++)
	{
		int x;
		cin >> x;
		if (i >= N)
		{
			t[i] = x;
			ans += (t[i - 1] < t[i] ? S * (t[i - 1] - t[i]) : T * (t[i - 1] - t[i]));
		}
	}

	while (Q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		ll a = query(l - 1), b = query(l);
		ll d1 = (a < b ? S * (a - b) : T * (a - b));
		a = query(r), b = query(r + 1);
		ll d2 = (a < b ? S * (a - b) : T * (a - b));
		ans -= d1 + d2;
		update(l, r, x);
		a = query(l - 1), b = query(l);
		d1 = (a < b ? S * (a - b) : T * (a - b));
		a = query(r), b = query(r + 1);
		d2 = (a < b ? S * (a - b) : T * (a - b));
		ans += d1 + d2;

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

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