Submission #691972

#	Time	Username	Problem	Language	Result	Execution time	Memory
691972		powerleo101	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	500 ms	27924 KiB

Main

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#define gi get_int()
#define int long long
const int MAXN = 1e6;
int get_int()
{
	int x = 0, y = 1;
	char ch = getchar();
	while (!isdigit(ch) && ch != '-')
		ch = getchar();
	if (ch == '-')
		 y = -1, ch = getchar();
	while (isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	return x * y;
}

int tree[MAXN][2][2], num[MAXN], n;
void push(int now, int mid)
{
	if (num[mid - 1] * num[mid] >= 0) {
		tree[now][0][0] = std::max(tree[now << 1][0][0] + tree[now << 1 | 1][0][0], tree[now << 1][0][1] + tree[now << 1 | 1][0][0]);
		tree[now][1][0] = std::max(tree[now << 1][1][0] + tree[now << 1 | 1][0][0], tree[now << 1][1][1] + tree[now << 1 | 1][0][0]);
		tree[now][0][1] = std::max(tree[now << 1][0][0] + tree[now << 1 | 1][0][1], tree[now << 1][0][1] + tree[now << 1 | 1][0][1]);
		tree[now][1][1] = std::max(tree[now << 1][1][0] + tree[now << 1 | 1][0][1], tree[now << 1][1][1] + tree[now << 1 | 1][0][1]);
	} else {
		tree[now][0][0] = std::max(tree[now << 1][0][1] + tree[now << 1 | 1][0][0], tree[now << 1][0][0] + tree[now << 1 | 1][1][0]);
		tree[now][1][0] = std::max(tree[now << 1][1][1] + tree[now << 1 | 1][0][0], tree[now << 1][1][0] + tree[now << 1 | 1][1][0]);
		tree[now][0][1] = std::max(tree[now << 1][0][1] + tree[now << 1 | 1][0][1], tree[now << 1][0][0] + tree[now << 1 | 1][1][1]);
		tree[now][1][1] = std::max(tree[now << 1][1][1] + tree[now << 1 | 1][0][1], tree[now << 1][1][0] + tree[now << 1 | 1][1][1]);
	}
}

int ABS(int u)
{
	return u < 0 ? -u : u;
}

void build(int now = 1, int lrange = 0, int rrange = n)
{
	if (lrange == rrange - 1) {
		tree[now][0][0] = ABS(num[lrange]);
		return ;
	}
	int mid = (lrange + rrange) / 2;
	build(now << 1, lrange, mid);
	build(now << 1 | 1, mid, rrange);
	push(now, mid);
}
void update(int p, int value, int now = 1, int lrange = 0, int rrange = n)
{
	if (p < lrange || p >= rrange)
		return ;
	if (lrange == rrange - 1) {
		tree[now][0][0] = ABS(num[lrange]);
		return ;
	}
	int mid = (lrange + rrange) / 2;
	update(p, value, now << 1, lrange, mid);
	update(p, value, now << 1 | 1, mid, rrange);
	push(now, mid);
	//std::cout << lrange << ' ' << rrange << ' ' << tree[now][0][0] << std::endl;
}

signed main()
{
#ifdef LOCAL_PROJECT
	freopen("code.in", "r", stdin);
	freopen("code.out", "w", stdout);
#endif

	n = gi;
	int Q = gi;
	for (int i = 0; i < n; i++)
		num[i] = gi;
	for (int i = n - 1; i > 0; i--)
		num[i] = num[i] - num[i - 1];
	num[0] = 0;
	build();
	while (Q--) {
		int l = gi - 1, r = gi, value = gi;
		num[l] += value;
		num[r] -= value;
		update(l, value);
		update(r, -value);
		std::cout << tree[1][1][0] << std::endl;
	}

	return 0;
}

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