Submission #1188064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188064		qrn	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	2 ms	4160 KiB

Main

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt int

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e9;
const intt mxN = 5e5 + 5;
const intt L = 21;

struct nod {
	char so,sa;
	intt vv, vy, yv, yy;
};

nod seg[4 * mxN];
vector<intt> A(mxN), AA(mxN);
intt N;

nod merge(nod &l, nod &r) {
	nod ret;
	if(l.sa != r.so) {
		ret.vv = max(l.vv + r.yv, l.vy + r.vv);
		ret.vy = max(l.vy + r.vy, l.vv + r.yy);
		ret.yv = max(l.yv + r.yv, l.yy + r.vv);
		ret.yy = max(l.yv + r.yy, l.yy + r.vy);
	} else {
		ret.vv = l.vv + r.vv;
		ret.vy = l.vv + r.vy;
		ret.yv = l.yv + r.vv;
		ret.yy = l.yv + r.vy;
	}
	ret.so = l.so;
	ret.sa = r.sa;
	return ret;
}

void build(intt node, intt l, intt r) {
	if(l == r) {
		if(AA[l] < 0) seg[node].so = seg[node].sa = '-';
		else seg[node].sa = seg[node].so = '+';
		seg[node].vv = seg[node].vy = seg[node].yy = seg[node].yv = 0;
		seg[node].vv = abs(AA[l]);
		// cout << seg[node].vv << ": " << seg[node].so << " " << seg[node].sa << endl;
		return;
	}
	
	intt mid = (l + r) / 2;
	build(node * 2, l, mid);
	build(node * 2 + 1, mid + 1, r);
	seg[node] = merge(seg[node * 2], seg[node * 2 + 1]);
}

void update(intt node, intt l, intt r, intt pos, intt val, intt type) {
	if(pos <= 0 || pos >= N+1) return;
	if(l == r) {
		if(type == 1) {
			if(seg[node].so == '-') {
				seg[node].vv += val;
			} else {
				if(seg[node].vv < val) {
					seg[node].so = seg[node].sa = '-';
					seg[node].vv = (val - seg[node].vv);
				} else {
					seg[node].vv -= val;
				}
			}
			if(seg[node].vv == 0) {
				seg[node].so = seg[node].sa = '+';
			}
		} else {
			if(seg[node].so == '+') {
				seg[node].vv += val;
			} else {
				if(seg[node].vv < val) {
					seg[node].so = seg[node].sa = '+';
					seg[node].vv = (val - seg[node].vv);
				} else {
					seg[node].vv -= val;
				}
			}
		}
		seg[node].vy = seg[node].yv = seg[node].yy = 0;
		// cout << "ASD: " << seg[node].vv << ": " << seg[node].so << endl;
		return;
	}

	intt mid = (l + r) / 2;
	if(pos <= mid) {
		update(node * 2, l, mid, pos, val, type);
	} else {
		update(node * 2 + 1, mid + 1, r, pos, val, type);
	}
	seg[node] = merge(seg[node * 2], seg[node * 2 + 1]);
}

intt get(intt node, intt l, intt r, intt ql, intt qr) {
	if(ql > r || qr < l || ql > qr) return 0;
	
	if(ql <= l && r <= qr) {
		return seg[node].vv;
	}
	
	intt mid = (l + r) / 2;
	return get(node * 2, l, mid, ql, qr) + get(node * 2 + 1, mid + 1, r, ql, qr);
}

void solve() {
	intt Q;
	cin >> N >> Q;
	for(intt i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for(intt i = 1; i <= N - 1; i++) {
		AA[i] = A[i] - A[i+1];
	}
	--N;
	build(1, 1, N);

	while(Q--) {
		intt l, r, val;
		cin >> l >> r >> val;
		--l;
		update(1, 1, N, l, val, 1);
		update(1, 1, N, r, val, 2);
		cout << get(1, 1, N, 1, N) << endl;
	}
}

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1;
	// cin >> tst;
	while(tst--) {
		solve();
	}
}

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