Submission #146630

#	Time	Username	Problem	Language	Result	Execution time	Memory
146630		pamaj	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	173 ms	10872 KiB

foehn_phenomena

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

const int maxn = 2e5 + 10;

#define int long long


typedef long long ll;
ll bit[maxn], v[maxn], n, q, s, t, ans;


ll calc(ll a, ll b)
{
	if(a < b) return -s*(abs(a - b));
	else return t*(abs(a - b));
}

void update(int id, ll val)
{
	for(int i = id; i <= n; i += i&-i)
	{
		bit[i] += val;
	}
}

int query(int id)
{
	ll ans = 0;

	for(int i = id; i > 0; i -= i&-i)
	{
		ans += bit[i];
	}

	return ans;
}

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

	cin >> n >> q >> s >> t;

	for(int i = 0; i <= n; i++)
	{
		cin >> v[i];
		if(i > 0) update(i, v[i]), update(i + 1, -v[i]);
	}

	for(int i = 0; i < n; i++)
		ans += calc(v[i], v[i + 1]);

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

		ll a, b, c, d;
		
		a = query(l - 1);
		b = query(l);
		c = query(r);
		d = query(r + 1);

		ans -= calc(a, b);
		if(r < n) ans -= calc(c, d);

		update(l, x);
		update(r + 1, -x);

		ans += (calc(a, b + x));
		if(r < n) ans += calc(c + x, d);
		cout << ans << "\n";
	}
}

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