Submission #1188085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188085		qrn	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	265 ms	33828 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 long long

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
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 = abs(max(l.vv + r.yv, l.vy + r.vv));
		ret.vy = abs(max(l.vy + r.vy, l.vv + r.yy));
		ret.yv = abs(max(l.yv + r.yv, l.yy + r.vv));
		ret.yy = abs(max(l.yv + r.yy, l.yy + r.vy));
	} else {
		ret.vv = abs(l.vv + r.vv);
		ret.vy = abs(l.vv + r.vy);
		ret.yv = abs(l.yv + r.vv);
		ret.yy = abs(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;
	// 7 4  - 6
	if(l == r) {
		if(type == 1) {
			if(seg[node].so == '-') {
				if(val < 0 && seg[node].vv + val < 0) {
					seg[node].so = seg[node].sa = '+';
					seg[node].vv = abs(val) - seg[node].vv;
				}
				else
				seg[node].vv += val;
			} else {
				if(val < 0) {
					seg[node].vv += abs(val);
					seg[node].vy = seg[node].yv = seg[node].yy = 0;
					return;
				} 
				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 == '+') {
				if(val < 0 && seg[node].vv + val < 0) {
					seg[node].so = seg[node].sa = '-';
					seg[node].vv = abs(val) - seg[node].vv;
				} 
				else
				seg[node].vv += val;
			} else {
				if(val < 0) {
					seg[node].vv += abs(val);
					seg[node].vy = seg[node].yv = seg[node].yy = 0;
					return;
				}
				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 = '+';
			}
		}
		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);

	vector<intt> ans;
	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);
		ans.pb(get(1,1,N,1,N));
	}
	// reverse(ALL(ans));
	for(intt i : ans) cout << i << 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: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55