Submission #487802

#	Time	Username	Problem	Language	Result	Execution time	Memory
487802		grt	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	969 ms	32260 KiB

Main

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200'000 + 10;
const ll INF = 1e18;
int n, q;
ll val[(1 << 18)];

struct Node {
	ll f[2][2];
	int l, r;
};

Node T[(1 << 19)];
int R;

Node combine(Node &a, Node &b) {
	Node c;
	for(int l : {0,1}) for(int r : {0,1}) c.f[l][r] = 0;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			for(int l1 : {0,1}) {
				for(int r1 : {0,1}) {
					if(l1 + r1 == 2 && (val[a.r] < 0 && val[b.l] > 0 || val[a.r] > 0 && val[b.l] < 0)) continue;
					c.f[l][r] = max(c.f[l][r], a.f[l][l1] + b.f[r1][r]);
				}
			}
		}
	}
	c.l = a.l;
	c.r = b.r;
	return c;
}

void upd(int a, ll x) {
	a += R;
	for(int l : {0,1}) {
		for(int r : {0,1}) {
			if(l != r) T[a].f[l][r] = 0;
			else if(r) T[a].f[l][r] = abs(x);
			else T[a].f[l][r] = 0;
		}
	}
	while(a > 1) {
		a /= 2;
		T[a] = combine(T[2*a], T[2*a+1]);
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i < n; ++i) {
		cin >> val[i];
	}
	for(int i = 0; i < n - 1; ++i) {
		val[i] -= val[i + 1];
	}
	val[n - 1] = 0;
	R = 1;
	while(R < n) R *= 2;
	for(int i = R; i < R * 2; ++i) {
		T[i].l = T[i].r = i - R;
	}
	for(int i = 0; i < R; ++i) {
		upd(i, val[i]);
	}
	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l-=2;
		if(l >= 0) {
			val[l] -= x;
			upd(l, val[l]);
		}
		r--;
		if(r < n - 1) {
			val[r] += x;
			upd(r, val[r]);
		}
		ll ans = 0;
		for(int a : {0,1}) for(int b : {0,1}) ans = max(ans, T[1].f[a][b]);
		cout << ans << "\n";
	}
	
}

Compilation message (stderr)

Main.cpp: In function 'Node combine(Node&, Node&)':
Main.cpp:40:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |      if(l1 + r1 == 2 && (val[a.r] < 0 && val[b.l] > 0 || val[a.r] > 0 && val[b.l] < 0)) continue;
      |                          ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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