Submission #987115

#	Time	Username	Problem	Language	Result	Execution time	Memory
987115		luffy_monkey	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	629 ms	51104 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")

// #define ll long long
#define int long long
#define ios ios_base::sync_with_stdio(0);cin.tie(0);

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);


template<typename T>
void max_self(T& a, T b) {
	if(a < b) {
		a = b;
	}
}

const int nax = 2e5 + 1;

struct Node {
	int ans[2][2] = {0};
	int sides[2] = {0};
	Node() {}
};
Node tree[4 * nax];

int sgn(int n) {
	return n >= 0 ? 1 : -1;
}
Node merge(Node left, Node right) {
	Node res;
	res.sides[0] = left.sides[0];
	res.sides[1] = right.sides[1];
	for(int l = 0; l < 2; ++l) {
		for(int r = 0; r < 2; ++r) {
			for(int ll = 0; ll < 2; ++ll) {
				for(int rr = 0; rr < 2; ++rr) {
					if(!r || !ll) { // one of the value isn't taken so you can just gather the two parts
						max_self(res.ans[l][rr], left.ans[l][r] + right.ans[ll][rr]);
					} else if(sgn(left.sides[1]) == sgn(right.sides[0])) { // you can merge here since the sign doesn't change
						max_self(res.ans[l][rr], left.ans[l][r] + right.ans[ll][rr]);
					}
				}
			}
		}
	}
	return res;
}
void upd(Node& cur, int v) { // only used in the case of leaf node
	cur.sides[0] += v;
	cur.sides[1] += v;
	assert(cur.sides[1] == cur.sides[0]);
	cur.ans[1][1] = abs(cur.sides[0]);
}

void upd(int node, int l, int r, int pos, int v) {
	if(r < pos || pos < l) return;
	if(l == r) {
		upd(tree[node], v);
		return;
	}
	int mid = (l + r) / 2;
	upd(node * 2, l, mid, pos, v);
	upd(node * 2 + 1, mid + 1, r, pos, v);
	tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
}

signed main()
{
	ios
	int n, q; cin >> n >> q;
	vector<int> a(n); for(int& x : a) cin >> x;
	vector<int> diff(n - 1);

	for(int i = 0; i < n - 1; ++i) {
		diff[i] = a[i + 1] - a[i];
		upd(1, 0, n - 2, i, diff[i]);
	}

	while(q--) {
		int l, r, x; cin >> l >> r >> x; l--, --r;
		if(l > 0)  {
			upd(1, 0, n - 2, l - 1, x);
		}
		if(r < n - 1)  {
			upd(1, 0, n - 2, r, -x);
		}
		int ans = 0;
		for(int l = 0; l < 2; ++l) {
			for(int r = 0; r < 2; ++r) {
				max_self(ans, tree[1].ans[l][r]);
			}
		}
		cout << ans << '\n';
	}
}

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