Submission #483873

#	Time	Username	Problem	Language	Result	Execution time	Memory
483873		Sohsoh84	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	455 ms	29512 KiB

Main

//: // ////: ///  / : //// / :
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;
#define int			ll

const ll MAXN = 1e6 + 10;

int n, q, A[MAXN], B[MAXN], sg[MAXN][4];

inline bool match(int x, int y) {
	if (x * y > 0) return true;
	return false;
}

/*
 * 0: 00
 * 1: 01
 * 2: 10
 * 3: 11
 * */

inline void upd(int& a, int b) {
	a = max(a, b);
}

inline void calc(int v, int i) {
	sg[v][0] = sg[v][1] = sg[v][2] = sg[v][3] = 0;
	
	for (int x = 0; x < 2; x++) {
		for (int y = 0; y < 2; y++) {
			if (!match(B[i], B[i + 1]) && x && y) continue;
			upd(sg[v][0], sg[v << 1][x] + sg[v << 1 | 1][y << 1]);
			upd(sg[v][1], sg[v << 1][x] + sg[v << 1 | 1][y << 1 | 1]);
			upd(sg[v][2], sg[v << 1][x | 2] + sg[v << 1 | 1][y << 1]);
			upd(sg[v][3], sg[v << 1][x | 2] + sg[v << 1 | 1][y << 1 | 1]);
		}
	}
}

void update(int ind, int val, int l = 1, int r = n, int v = 1) {
	if (l == r) {
		B[l] += val;
		sg[v][3] = abs(B[l]);
	} else {
		int mid = (l + r) >> 1;
		if (ind <= mid) update(ind, val, l, mid, v << 1);
		else update(ind, val, mid + 1, r, v << 1 | 1);

		calc(v, mid);
	}

	// cerr << v << " : " << l << sep << r << " : " << sg[v][0] << sep << sg[v][1] << sep << sg[v][2] << sep << sg[v][3] << endl;
}

inline int solve() {
	int l, r, x;
	cin >> l >> r >> x;
	if (l > 1) update(l - 1, x);
	if (r <= n) update(r, -x);

	cout << max({sg[1][0], sg[1][1], sg[1][2], sg[1][3]}) << endl;
	return 0;
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> A[i];
	n--;
	for (int i = 1; i <= n; i++) update(i, A[i + 1] - A[i]);

	if (!n) {
		while (q--) cout << 0 << endl;
		return 0;
	}

	while (q--) solve();
	return 0;
}

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