Submission #810376

#	Time	Username	Problem	Language	Result	Execution time	Memory
810376		tlnk07	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	2 ms	212 KiB

Main

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

long long n, q, a[200001];
pair<int, int> tree[1000001];

void build(int id, int l, int r)
{
	if(l == r)
	{
		tree[id] = {a[l], a[l]};
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	tree[id].first = max(tree[id * 2].first, tree[id * 2 + 1].first);
	tree[id].second = min(tree[id * 2].second, tree[id * 2 + 1].second);
}

void update(int id, int l, int r, int posl, int posr, int val)
{
	if(posr < l || posl > r)	return;
	if(r == l)
	{
		tree[id].first += val;
		tree[id].second += val;
		return;
	}
	int mid = (l + r) / 2;
	update(id * 2, l, mid, posl, posr, val);
	update(id * 2 + 1, mid + 1, r, posl, posr, val);
	tree[id].first = max(tree[id * 2].first, tree[id * 2 + 1].first);
	tree[id].second = min(tree[id * 2].second, tree[id * 2 + 1].second);
}

pair<int, pair<int, int>> get(int id, int l, int r, int posl, int posr)
{
	if(posr < l || posl > r)	return {0, {0, 0}};
	if(r == l)	return {0, tree[id]};
	int mid = (l + r) / 2;
	pair<int, pair<int, int>> temp1 = get(id * 2, l, mid, posl, posr), temp2 = get(id * 2 + 1, mid + 1, r, posl, posr);
	return {max(max(temp1.second.first, temp2.second.first) - min(temp1.second.second, temp2.second.second), temp1.first + temp2.first), {max(temp1.second.first, temp2.second.first), min(temp1.second.second, temp2.second.second)}};
}

int main()
{
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)	cin >> a[i];
	build(1, 1, n);
	while(q--)
	{
		long long x, y, z;
		cin >> x >> y >> z;
		update(1, 1, n, x, y, z);
		cout << get(1, 1, n, 1, n).first << "\n";
	}
}

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