Submission #585382

#	Time	Username	Problem	Language	Result	Execution time	Memory
585382		jairRS	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	0 / 100	1022 ms	30980 KiB

foehn_phenomena

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(s) s.begin(), s.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

ll n, q, s, t;

ll getTempDiff(ll heightLeft, ll heightRight)
{
	ll heightDif = abs(heightLeft - heightRight), res = 0;
	if (heightLeft < heightRight)
		res -= s * heightDif;
	else
		res += t * heightDif;
	return res;
}

struct SegmentTree
{
	struct node
	{
		ll temp, heightLeft, heightRight;
		bool neutral = false;
	};

	vector<node> tree;
	vector<ll> lazy;
	int power2 = 1, size;
	SegmentTree(int N)
	{
		while (power2 < N)
			power2 *= 2;
		size = 2 * power2 - 1;
		tree = vector<node>(size + 1, {0, 0, 0, 1});
		lazy = vector<ll>(size + 1, 0);
	}

	node merge(node &a, node &b)
	{
		if (a.neutral)
			return b;
		if (b.neutral)
			return a;

		node res;
		res.temp = a.temp + b.temp + getTempDiff(a.heightRight, b.heightLeft);
		res.heightLeft = a.heightLeft;
		res.heightRight = b.heightRight;
		return res;
	}

	void pushLazy(int i)
	{
		tree[i].heightLeft += lazy[i];
		tree[i].heightRight += lazy[i];
		if (i * 2 + 1 <= size)
		{
			lazy[i * 2] += lazy[i];
			lazy[i * 2 + 1] += lazy[i];
		}
		lazy[i] = 0;
	}

	void update(int i, ll k)
	{
		int in = i + size / 2;
		tree[in].heightLeft += k;
		tree[in].heightRight += k;
		tree[in].neutral = false;

		int inCopy = in;
		vi indices;
		while (inCopy > 0)
		{
			indices.pb(inCopy);
			inCopy /= 2;
		}

		for (int j = indices.size() - 1; j >= 0; j--)
			pushLazy(indices[j]);

		in /= 2;
		while (in > 0)
		{
			tree[in] = merge(tree[in * 2], tree[in * 2 + 1]);
			in /= 2;
		}
	}

	void update(int l, int r, ll k)
	{
		update(1, 1, power2, l, r, k);

		vi toUpdate = {l - 1, l, l + 1, r - 1, r, r + 1};
		for (int i : toUpdate)
			if (1 <= i && i <= power2)
				update(i, 0);
	}

	void update(int i, int l, int r, int ql, int qr, ll k)
	{
		if (ql > r || qr < l)
			return;
		if (ql <= l && r <= qr)
		{
			lazy[i] += k;
			return;
		}

		int mid = (l + r) / 2;
		update(i * 2, l, mid, ql, qr, k);
		update(i * 2 + 1, mid + 1, r, ql, qr, k);
	}

	node query(int i, int l, int r, int ql, int qr)
	{
		pushLazy(i);

		if (ql > r || qr < l)
			return node({0, 0, 0, 1});
		if (ql <= l && r <= qr)
			return tree[i];

		int mid = (l + r) / 2;
		node query1 = query(i * 2, l, mid, ql, qr);
		node query2 = query(i * 2 + 1, mid + 1, r, ql, qr);
		return merge(query1, query2);
	}
};

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

	cin >> n >> q >> s >> t;
	vector<ll> height(n + 1, 0);
	for (int i = 0; i <= n; i++)
		cin >> height[i];

	SegmentTree segTree(n + 1);
	for (int i = 1; i <= n + 1; i++)
		segTree.update(i, height[i - 1]);

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

		segTree.update(l, r, k);
		cout << segTree.query(1, 1, segTree.power2, 1, n + 1).temp << '\n';
	}
}

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