oj.uz

Submission #369305

# Submission time Handle Problem Language Result Execution time Memory
369305 2021-02-21T09:12:01 Z GioChkhaidze Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1396 ms 50300 KB 
#include <bits/stdc++.h>

#define ll long long
#define lf (h << 1)
#define rf ((h << 1) | 1)

using namespace std;

const int N = 2e5 + 5;

ll n, q, a[N], d[N], v[4 * N][3][3];

void upd(int h, int l, int r, int id) {
	if (id < l || r < id) return ;
	if (l == id && id == r) {
		v[h][1][1] = abs(d[id]);
		return ;
	}
	int m = (l + r) >> 1;
	upd(lf, l, m, id);
	upd(rf, m + 1, r, id);
	
	v[h][1][1] = max(v[lf][1][0] + v[rf][1][1], v[lf][1][1] + v[rf][0][1]);
	v[h][1][0] = max(v[lf][1][0] + v[rf][1][0], v[lf][1][1] + v[rf][0][0]);
	v[h][0][1] = max(v[lf][0][0] + v[rf][1][1], v[lf][0][1] + v[rf][0][1]);
	v[h][0][0] = max(v[lf][0][0] + v[rf][1][0], v[lf][0][1] + v[rf][0][0]);
	
	if ((d[m] >= 0 && d[m + 1] >= 0) || (d[m] <= 0 && d[m + 1] <= 0)) {
		v[h][1][1] = max(v[lf][1][0], v[lf][1][1]) + max(v[rf][0][1], v[rf][1][1]);
		v[h][1][0] = max(v[lf][1][0], v[lf][1][1]) + max(v[rf][0][0], v[rf][1][0]);
		v[h][0][1] = max(v[lf][0][0], v[lf][0][1]) + max(v[rf][0][1], v[rf][1][1]);
		v[h][0][0] = max(v[lf][0][0], v[lf][0][1]) + max(v[rf][0][0], v[rf][1][0]);
	}
}

main () {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i < n; ++i) {
		d[i] = a[i + 1] - a[i];
		upd(1, 1, n - 1, i);
	}
	
	for (int i = 1; i <= q; ++i) {
		int l, r, x;
		cin >> l >> r >> x;

		d[r] -= x;
		upd(1, 1, n - 1, r);
		
		if (l - 1) {
			d[l - 1] += x;
			upd(1, 1, n - 1, l - 1);
		}
	
		cout << max(max(v[1][0][0], v[1][1][1]), max(v[1][0][1], v[1][1][0])) << "\n";
	}
}

Compilation message

Main.cpp:36:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main () {
      |       ^

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 15 ms 1132 KB Output is correct
8 Correct 16 ms 1160 KB Output is correct
9 Correct 15 ms 1132 KB Output is correct
10 Correct 15 ms 1132 KB Output is correct
11 Correct 15 ms 1152 KB Output is correct
12 Correct 15 ms 1132 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 15 ms 1132 KB Output is correct
8 Correct 16 ms 1160 KB Output is correct
9 Correct 15 ms 1132 KB Output is correct
10 Correct 15 ms 1132 KB Output is correct
11 Correct 15 ms 1152 KB Output is correct
12 Correct 15 ms 1132 KB Output is correct
13 Correct 1396 ms 49620 KB Output is correct
14 Correct 1339 ms 49900 KB Output is correct
15 Correct 1343 ms 49580 KB Output is correct
16 Correct 1340 ms 50028 KB Output is correct
17 Correct 1352 ms 49492 KB Output is correct
18 Correct 1288 ms 50300 KB Output is correct