Submission #985254

#	Time	Username	Problem	Language	Result	Execution time	Memory
985254		michified	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	348 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

struct node_t {
	ll nlnr, nlyr, ylnr, ylyr, l, r;
};

int n, q;
vector<node_t> st;
vector<ll> d;

node_t merge(node_t& a, node_t& b) {
	node_t res;
	bool can = (a.r >= 0 and b.l >= 0) or (a.r <= 0 and b.l <= 0);
	res.nlnr = max(max(a.nlyr + b.nlnr, a.nlnr + b.nlnr), 
			   max(a.nlnr + b.ylnr, can ? a.nlyr + b.ylnr : -1));
	res.ylnr = max(max(a.ylyr + b.nlnr, a.ylnr + b.nlnr), 
			   max(a.ylnr + b.ylnr, can ? a.ylyr + b.ylnr : -1));
	res.nlyr = max(max(a.nlyr + b.nlyr, a.nlnr + b.nlyr), 
			   max(a.nlnr + b.ylyr, can ? a.nlyr + b.ylyr : -1));
	res.ylyr = max(max(a.ylyr + b.nlyr, a.ylnr + b.nlyr), 
			   max(a.ylnr + b.ylyr, can ? a.ylyr + b.ylyr : -1));
	return res;
}

void build(int id, int l, int r) {
	if (l == r) {
		st[id] = {0, 0, 0, abs(d[l]), d[l], d[l]};
		return;
	}
	int mid = (l + r) / 2;
	build(lid, l, mid);
	build(rid, mid + 1, r);
	st[id] = merge(st[lid], st[rid]);
}

void upd(int id, int l, int r, int i, int val) {
	if (l == r) {
		d[l] += val;
		st[id] = {0, 0, 0, abs(d[l]), d[l], d[l]};
		return;
	}
	int mid = (l + r) / 2;
	if (i <= mid) upd(lid, l, mid, i, val);
	else upd(rid, mid + 1, r, i, val);
	st[id] = merge(st[lid], st[rid]);
}

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

	cin >> n >> q;
	int i, m;
	vector<ll> a(n);
	for (i = 0; i < n; i++) cin >> a[i];
	m = n - 1;
	d.resize(m);
	st.resize(m * 4);
	for (i = 0; i < m; i++) d[i] = a[i + 1] - a[i];
	build(0, 0, m - 1);
	vector<vector<int>> ques(q, vector<int>(3));
	for (i = 0; i < q; i++) cin >> ques[i][0] >> ques[i][1] >> ques[i][2];
	for (auto& que : ques) {
		if (que[0] > 1) upd(0, 0, m - 1, que[0] - 2, que[2]);
		if (que[1] < n) upd(0, 0, m - 1, que[1] - 1, -que[2]);
		cout << st[0].ylyr << endl;
	}
	return 0;
}

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