Submission #512593

#	Time	Username	Problem	Language	Result	Execution time	Memory
512593		starchan	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	1053 ms	89852 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e17
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)1e6
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may change to that 99.. number.
struct node
{
	int st[3][3];
	node(int get = -INF)
	{
		for(int i = 0; i <= 2; i++)
		{
			for(int j = 0; j <= 2; j++)
				st[i][j] = -INF;
		}
		if(get == -INF)
			return;
		st[0][1] = st[1][0] = get;
		st[1][1] = 0;
		st[1][2] = st[2][1] = -get;
		return;
	}
};
node merge(node n1, node n2)
{
	node n3(-INF);
	for(int i = 0; i <= 2; i++)
	{
		for(int j = 0; j <= 2; j++)
		{
			n3.st[i][j] = max(n1.st[i][j], n2.st[i][j]);
			for(int k = 0; k <= 2; k++)
			{
				int optmilk = n1.st[i][2-k]+n2.st[k][j];
				n3.st[i][j] = max(n3.st[i][j], optmilk);
			}
		}
	}
	return n3;
}
int extract(node n)
{
	return n.st[1][1];
} 
struct segment_tree
{
	vector<node> tree;
	vector<int> delta;
	void init()
	{
		tree.resize(LMX);
		delta.assign(LMX, 0);
	}
	void paint(int x, int id)
	{
		for(int i = 0; i <= 2; i++)
		{
			for(int j = 0; j <= 2; j++)
				tree[id].st[i][j]-=(i+j-2)*x;
		}
		return;
	}
	void push(int id)
	{
		delta[2*id]+=delta[id];
		delta[2*id+1]+=delta[id];
		paint(delta[id], 2*id);
		paint(delta[id], 2*id+1);
		delta[id] = 0;
		return;
	}
	void build(const vector<int> &a, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{	
			tree[id] = node(a[m]);
			return;
		}
		build(a, 2*id, l, m);
		build(a, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}
	void upd(int ql, int qr, int X, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(ql <= l && r <= qr)
		{
			paint(X, id);
			delta[id]+=X;
			return;
		}
		if(qr < l || r < ql)
			return;
		push(id);
		upd(ql, qr, X, 2*id, l, m);
		upd(ql, qr, X, 2*id+1, m+1, r);
		tree[id] = merge(tree[2*id], tree[2*id+1]);
		return;
	}
};
signed main()
{
	fast();
	segment_tree work;
	work.init();
	int n, q;
	cin >> n >> q;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	work.build(a, 1, 1, n);
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		work.upd(l, r, x, 1, 1, n);
		cout << extract(work.tree[1]) << "\n";
	}
	return 0;
}

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