Submission #369306

#	Time	Username	Problem	Language	Result	Execution time	Memory
369306		GioChkhaidze	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	682 ms	43500 KiB

Main

#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 (stderr)

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

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