Submission #868000

#	Time	Username	Problem	Language	Result	Execution time	Memory
868000		_hbk06	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	504 ms	186192 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "recipe"

using namespace std;
const int mxN = 5e5 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

#define int long long

struct node {
	int dp[3][3];
	int val[2];
	node(int u = 0) {
		memset(dp,0,sizeof dp);
		dp[1][1] = abs(u);
		val[0] = val[1] = u;
	}
}Node[4 * mxN];

int n;
int q;
int a[mxN];


node merge(const node &x,const node &y) {
	node res;
	res.val[0] = x.val[0];
	res.val[1] = y.val[1];
	for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) {
		maximize(res.dp[i][j],x.dp[i][0] + y.dp[0][j]);
		maximize(res.dp[i][j],x.dp[i][0] + y.dp[1][j]);
		maximize(res.dp[i][j],x.dp[i][1] + y.dp[0][j]);
		if(1LL * x.val[1] * y.val[0] >= 0) maximize(res.dp[i][j],x.dp[i][1] + y.dp[1][j]);
	} 
	return res;
}

void built(int id,int l,int r) {
	if(l == r) {
		Node[id] = node(a[l]);
		return;
	}
	int mid = (l + r) >> 1;
	built(id * 2,l,mid);
	built(id * 2 + 1,mid + 1,r);
	Node[id] = merge(Node[id * 2],Node[id * 2 + 1]);
}

void update(int id,int l,int r,int u) {
	if(u < l || u > r) return;
	if(l == r) {
		Node[id] = node(a[u]);
		return;
	}
	int mid = (l + r) >> 1;
	update(id * 2,l,mid,u);
	update(id * 2 + 1,mid + 1,r,u);
	Node[id] = merge(Node[id * 2],Node[id * 2 + 1]);
}

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
	built(1,1,n - 1);
// cout << max(Node[1].dp[0][0],max(Node[1].dp[0][1],max(Node[1].dp[1][0],Node[1].dp[1][1])));
	while(q--) {
		int l,r,x;
		cin >> l >> r >> x;
		if(l > 1) {
			a[l - 1] += x;
			update(1,1,n - 1,l - 1);
		}
		a[r] -= x;
		if(r < n) update(1,1,n - 1,r);
		cout << max(Node[1].dp[0][0],max(Node[1].dp[0][1],max(Node[1].dp[1][0],Node[1].dp[1][1])));
		cout << '\n';
	}
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	//freopen(TASK".inp","r",stdin);
	//freopen(TASK".out","w",stdout);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

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