Submission #753553

#	Time	Username	Problem	Language	Result	Execution time	Memory
753553		tcmmichaelb139	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	340 KiB

Main

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

struct Node {
	long long mx;
	long long mxl;
	long long mxr;
	long long mxlr;
	int l;
	int r;
};

template <class T, int N>
struct Seg {
	static_assert(__builtin_popcount(N) == 1);
	const T ID = {0, 0, 0, 0, 0, 0};
	T cmb(T a, T b) {
		Node n;
		n.mx = max(a.mxr + b.mx, a.mx + b.mxl);
		n.mxl = max(a.mxl + max(b.mxl, b.mx), a.mxlr + b.mx);
		n.mxr = max(max(a.mxr, a.mx) + b.mxr, a.mx + b.mxlr);
		n.mxlr = max(a.mxlr + max(b.mxr, b.mx), max(a.mxl, a.mx) + b.mxlr);
		n.l = a.l;
		n.r = b.r;
		if (a.r == b.l) {
			n.mx = max(n.mx, a.mxr + b.mxl);
			n.mxl = max(n.mxl, a.mxlr + b.mxl);
			n.mxr = max(n.mxr, a.mxr + b.mxlr);
			n.mxlr = max(n.mxlr, a.mxlr + b.mxlr);
		}
		return n;
	}
	T seg[2 * N];
	Seg() {
		for (int i = 0; i < 2 * N; i++)
			seg[i] = ID;
	}
	void pull(int p) { seg[p] = cmb(seg[2 * p], seg[2 * p + 1]); }
	void print() {
		for (int i = N; i < 2 * N; i++) cout << seg[i].mxlr << ' ' << seg[i].l << '\n';
	}
	void build(vector<T> &v, int p = 1, int L = 0, int R = N - 1) {
		if (L == R) {
			if (size(v) > L)
				seg[p] = v[L];
		} else {
			int M = (L + R) / 2;
			build(v, 2 * p, L, M);
			build(v, 2 * p + 1, M + 1, R);
			pull(p);
		}
	}
	void upd(int v, long long val, int p = 1, int L = 0, int R = N - 1) {
		if (L == R) {
			seg[p].mxlr *= seg[p].l;
			seg[p].mxlr += val;
			if (seg[p].mxlr < 0)
				seg[p].l = seg[p].r = -1;
			if (seg[p].mxlr > 0)
				seg[p].l = seg[p].r = 1;
			seg[p].mxlr = abs(seg[p].mxlr);
		} else {
			int M = (L + R) / 2;
			if (v <= M)
				upd(v, val, 2 * p, L, M);
			else
				upd(v, val, 2 * p + 1, M + 1, R);
			pull(p);
		}
	}
	T query(int lo, int hi, int p = 1, int L = 0, int R = N - 1) {
		if (lo > R || L > hi) return ID;
		if (lo <= L && R <= hi) return seg[p];
		int M = (L + R) / 2;
		return cmb(query(lo, hi, 2 * p, L, M), query(lo, hi, 2 * p + 1, M + 1, R));
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, q;
	cin >> n >> q;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	vector<Node> diff(n - 1);
	for (int i = 0; i < n - 1; i++) {
		int mult = 1;
		if (v[i + 1] < v[i]) mult = -1;
		diff[i] = {0, 0, 0, abs(v[i + 1] - v[i]), mult, mult};
	}

	Seg<Node, 8> seg;
	seg.build(diff);

	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;

		l--, r--;
		if (l != 0) seg.upd(l - 1, x);
		if (r != n - 1) seg.upd(r, -x);

		cout << seg.query(0, n).mxlr << '\n';
	}
}

Compilation message (stderr)

Main.cpp: In instantiation of 'void Seg<T, N>::build(std::vector<_Tp>&, int, int, int) [with T = Node; int N = 8]':
Main.cpp:97:16:   required from here
Main.cpp:44:16: warning: comparison of integer expressions of different signedness: 'std::vector<Node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |    if (size(v) > L)
      |        ~~~~~~~~^~~

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