Submission #1240233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240233		ssitaram	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	446 ms	83376 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

struct segtree {
	int n, sz;
	vector<vector<vector<ll>>> sm;
	vector<ll> D;

	segtree(int sz) : sz(sz) {
		n = 1;
		while (n < sz) n *= 2;
		sm.resize(2 * n - 1, vector<vector<ll>>(2, vector<ll>(2)));
		D.resize(n);
	}

	void upd(int node, int l, int r, int i, int x) {
		if (r == l + 1) {
			D[i] += x;
			sm[node][0][0] = abs(D[i]);
			return;
		}
		int m = (l + r) / 2;
		if (i < m) {
			upd(node * 2 + 1, l, m, i, x);
		} else {
			upd(node * 2 + 2, m, r, i, x);
		}
		bool v = ((D[m] > 0 && D[m - 1] < 0) || (D[m] < 0 && D[m - 1] > 0));
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				if (v) {
					sm[node][j][k] = max(sm[node * 2 + 1][j][0] + sm[node * 2 + 2][1][k], sm[node * 2 + 1][j][1] + sm[node * 2 + 2][0][k]);
				} else {
					sm[node][j][k] = sm[node * 2 + 1][j][0] + sm[node * 2 + 2][0][k];
				}
			}
		}
	}

	void upd(int i, int x) {
		if (i < 0 || i >= sz) return;
		upd(0, 0, n, i, x);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q; cin >> n >> q;
	int p = -1;
	segtree st(n - 1);
	for (int i = 0; i < n; ++i) {
		int v; cin >> v;
		if (i > 0) {
			st.upd(i - 1, v - p);
		}
		p = v;
	}
	while (q--) {
		int l, r, x; cin >> l >> r >> x;
		--l; --r;
		st.upd(l - 1, x);
		st.upd(r, -x);
		cout << st.sm[0][0][0] << '\n';
	}
	return 0;
}

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