제출 #670612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670612		kirakaminski968	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	694 ms	50204 KiB

Main

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

//BeginCodeSnip{Segtree Node}
struct Node
{
	ll borders[2] = {};  // border values of segment
	ll dp[2][2] = {};  // take/not-take left and right border values
	Node() {}
	Node(ll v)
	{
		borders[0] = borders[1] = v;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[0][0] = 0;
		dp[1][1] = abs(v);
	}
	// assume current is left
	Node comb(Node &other)
	{
		Node ret;
		ret.borders[0] = borders[0];
		ret.borders[1] = other.borders[1];
		// [	 ][	 ]
		// l	 mo	 r
		// m and o same -> taken segments are combined
		for (int l = 0; l < 2; l++)
		{
			for (int m = 0; m < 2; m++)
			{
				for (int o = 0; o < 2; o++)
				{
					for (int r = 0; r < 2; r++)
					{
						if (m && o)
						{
							// it's never optimal to take two opposite sign values
							if ((borders[1] < 0) == (other.borders[0] < 0))
							{
								ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
							}
						}
						else
						{
							ret.dp[l][r] = max(ret.dp[l][r], dp[l][m] + other.dp[o][r]);
						}
					}
				}
			}
		}
		return ret;
	}

	// modify a single-element Node segment by +v
	void upd(ll v)
	{
		borders[0] += v;
		borders[1] += v;
		dp[1][1] = abs(borders[0]);
	}
};
//EndCodeSnip

//BeginCodeSnip{Segtree}
struct SegTree
{
	Node val;
	int gL, gR, mid;
	SegTree *left, *right;
	SegTree(int l, int r, vector<Node> &nums)
	{
		gL = l;
		gR = r;
		mid = (gL + gR) / 2;
		if (l == r)
		{
			val = nums[l];
		}
		else
		{
			left = new SegTree(l, mid, nums), right = new SegTree(mid + 1, r, nums);
			val = left->val.comb(right->val);
		}
	}

	void update(int idx, ll updval)
	{
		if (gL == gR)
		{
			val.upd(updval);
		}
		else
		{
			if (idx <= (gL + gR) / 2)
			{
				left->update(idx, updval);
			}
			else
			{
				right->update(idx, updval);
			}
			val = left->val.comb(right->val);
		}
	}
};
//EndCodeSnip

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	vector<Node> D(N - 1);
	int a;
	cin >> a;
	// compute difference array
	for (int i = 0; i < N - 1; i++)
	{
		int b;
		cin >> b;
		D[i] = Node(b - a);
		swap(a, b);
	}

	// a_(i + 1) - a(i)
	SegTree sgt(0, N - 2, D);
	for (int q = 0; q < Q; q++)
	{
		int l;
		int r;
		ll x;
		cin >> l >> r >> x;
		l--, r--;

		if (l - 1 >= 0)
		{
			sgt.update(l - 1, x);
		}
		if (r < N - 1)
		{
			sgt.update(r, -x);
		}
		cout << sgt.val.dp[1][1] << '\n';
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55