Submission #1152909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152909		siewjh	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	417 ms	37792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
ll diff[MAXN];
int sign(ll x){
	return x > 0;
}
struct vals{
	ll xx, xo, ox, oo;
};
struct node{
	int s, e, m; vals v;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e; m = (s + e) >> 1;
		if (s == e) v = {0, 0, 0, abs(diff[s])};
		else{
			l = new node(s, m); r = new node(m + 1, e);
			v = merge(l->v, r->v);
		}
	}
	vals merge(vals a, vals b){
		vals res;
		if (sign(diff[m]) == sign(diff[m + 1])){
			res.xx = a.xo + b.ox;
			res.xo = a.xo + b.oo;
			res.ox = a.oo + b.ox;
			res.oo = a.oo + b.oo;
		}
		else{
			res.xx = max(a.xo + b.xx, a.xx + b.ox);
			res.xo = max(a.xo + b.xo, a.xx + b.oo);
			res.ox = max(a.oo + b.xx, a.ox + b.ox);
			res.oo = max(a.oo + b.xo, a.ox + b.oo);
		}
		return res;
	}
	void update(int x){
		if (s == e){
			v = {0, 0, 0, abs(diff[s])};
			return;
		}
		else if (x <= m) l->update(x);
		else r->update(x);
		v = merge(l->v, r->v);
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int nums, queries; cin >> nums >> queries;
	vector<ll> vec(nums + 1);
	for (int i = 1; i <= nums; i++) cin >> vec[i];
	for (int i = 2; i <= nums; i++) diff[i] = vec[i] - vec[i - 1];
	node *root = new node(2, nums);
	while (queries--){
		int l, r; ll x; cin >> l >> r >> x; r++;
		if (l != 1){
			diff[l] += x; root->update(l);
		}
		if (r != nums + 1){
			diff[r] -= x; root->update(r);
		}
		cout << root->v.oo << '\n';
	}
}

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