oj.uz

Submission #670612

# Submission time Handle Problem Language Result Execution time Memory
670612 2022-12-09T18:11:49 Z kirakaminski968 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 694 ms 50204 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 6 ms 1072 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 6 ms 980 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 6 ms 1072 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 6 ms 980 KB Output is correct
13 Correct 643 ms 50076 KB Output is correct
14 Correct 662 ms 50116 KB Output is correct
15 Correct 694 ms 50168 KB Output is correct
16 Correct 654 ms 50124 KB Output is correct
17 Correct 644 ms 50168 KB Output is correct
18 Correct 599 ms 50204 KB Output is correct