Submission #482776

#	Time	Username	Problem	Language	Result	Execution time	Memory
482776		alireza_kaviani	Sjeckanje (COCI21_sjeckanje)	C++11	0 / 110	1 ms	332 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
inline void setmax(long long &a, long long b) {
	a = max(a, b);
}
 
constexpr int N = 2e5 + 10, INF = 1e17;
 
struct Node {
	long long dp[3][3], lz; //0: negative 2: positive
	
	inline void apply(long long x) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (dp[i][j] <= -INF) {
					continue;
				}
				dp[i][j] += 1ll * x * (i - 1 + j - 1);
				setmax(dp[i][j], -INF);
			}
		}
		lz += x;
	}
};
 
Node t[N << 2];
 
int n, q, a[N];
 
inline void push(int c, int l, int r) {
	if (t[c].lz != 0) {
		t[l].apply(t[c].lz);
		t[r].apply(t[c].lz);
		t[c].lz = 0;
	}	
}
 
inline void pull(int c, int l, int r) {
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			t[c].dp[i][j] = -INF;
			setmax(t[c].dp[i][j], t[l].dp[i][1] + t[r].dp[1][j]);
			setmax(t[c].dp[i][j], t[l].dp[i][0] + t[r].dp[2][j]);
			setmax(t[c].dp[i][j], t[l].dp[i][2] + t[r].dp[0][j]);
		//	setmax(t[c].dp[i][j], t[l].dp[i][j] + t[r].dp[1][1]);
		//	setmax(t[c].dp[i][j], t[l].dp[1][1] + t[r].dp[i][j]);
		}
	}
}
 
void build(int c, int b, int e) {
	if (e - b == 1) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				t[c].dp[i][j] = -INF;
			}
		}
		t[c].dp[1][1] = 0;
		t[c].dp[1][2] = t[c].dp[2][1] = a[b];
		t[c].dp[1][0] = t[c].dp[0][1] = -a[b];
		return;
	}
	int m = ((b + e) >> 1), l = (c << 1), r =  (l | 1);
	build(l, b, m);
	build(r, m, e);
	pull(c, l, r);
}
 
void update(int c, int b, int e, int u, int v, long long x) {
	if (e <= u || v <= b) {
		return;
	}
	if (u <= b && e <= v) {
		t[c].apply(x);
		return;
	}
	int m = ((b + e) >> 1), l = (c << 1), r = (l | 1);
	push(c, l, r);
	update(l, b, m, u, v, x);
	update(r, m, e, u, v, x);
	pull(c, l, r);
}
 
int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	build(1, 0, n);
	
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		--l;
		update(1, 0, n, l, r, x);
		assert(t[1].dp[1][1] >= 0);
		cout << t[1].dp[1][1] << '\n';
	}
}

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