oj.uz

Submission #369306

# Submission time Handle Problem Language Result Execution time Memory
369306 2021-02-21T09:12:45 Z GioChkhaidze Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 682 ms 43500 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 () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	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 1 ms 364 KB Output is correct
4 Correct 1 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 1 ms 364 KB Output is correct
4 Correct 1 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 6 ms 1004 KB Output is correct
8 Correct 6 ms 1004 KB Output is correct
9 Correct 6 ms 1004 KB Output is correct
10 Correct 6 ms 1004 KB Output is correct
11 Correct 6 ms 1004 KB Output is correct
12 Correct 5 ms 1004 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 1 ms 364 KB Output is correct
4 Correct 1 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 6 ms 1004 KB Output is correct
8 Correct 6 ms 1004 KB Output is correct
9 Correct 6 ms 1004 KB Output is correct
10 Correct 6 ms 1004 KB Output is correct
11 Correct 6 ms 1004 KB Output is correct
12 Correct 5 ms 1004 KB Output is correct
13 Correct 682 ms 43464 KB Output is correct
14 Correct 664 ms 43404 KB Output is correct
15 Correct 676 ms 43436 KB Output is correct
16 Correct 649 ms 43372 KB Output is correct
17 Correct 671 ms 43500 KB Output is correct
18 Correct 586 ms 43500 KB Output is correct