oj.uz

Submission #691972

# Submission time Handle Problem Language Result Execution time Memory
691972 2023-02-01T03:57:15 Z powerleo101 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 500 ms 27924 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 212 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 212 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 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 704 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 6 ms 700 KB Output is correct
10 Correct 6 ms 724 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 704 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7 ms 704 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 6 ms 700 KB Output is correct
10 Correct 6 ms 724 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 704 KB Output is correct
13 Correct 489 ms 27424 KB Output is correct
14 Correct 494 ms 27316 KB Output is correct
15 Correct 500 ms 27468 KB Output is correct
16 Correct 476 ms 27320 KB Output is correct
17 Correct 466 ms 27288 KB Output is correct
18 Correct 471 ms 27924 KB Output is correct