oj.uz

Submission #987115

# Submission time Handle Problem Language Result Execution time Memory
987115 2024-05-21T23:40:44 Z luffy_monkey Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 629 ms 51104 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 38232 KB Output is correct
2 Correct 9 ms 38136 KB Output is correct
3 Correct 8 ms 37980 KB Output is correct
4 Correct 7 ms 38036 KB Output is correct
5 Correct 9 ms 37980 KB Output is correct
6 Correct 9 ms 37976 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 38232 KB Output is correct
2 Correct 9 ms 38136 KB Output is correct
3 Correct 8 ms 37980 KB Output is correct
4 Correct 7 ms 38036 KB Output is correct
5 Correct 9 ms 37980 KB Output is correct
6 Correct 9 ms 37976 KB Output is correct
7 Correct 13 ms 37976 KB Output is correct
8 Correct 13 ms 37980 KB Output is correct
9 Correct 13 ms 37980 KB Output is correct
10 Correct 13 ms 38044 KB Output is correct
11 Correct 13 ms 37976 KB Output is correct
12 Correct 12 ms 38232 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 38232 KB Output is correct
2 Correct 9 ms 38136 KB Output is correct
3 Correct 8 ms 37980 KB Output is correct
4 Correct 7 ms 38036 KB Output is correct
5 Correct 9 ms 37980 KB Output is correct
6 Correct 9 ms 37976 KB Output is correct
7 Correct 13 ms 37976 KB Output is correct
8 Correct 13 ms 37980 KB Output is correct
9 Correct 13 ms 37980 KB Output is correct
10 Correct 13 ms 38044 KB Output is correct
11 Correct 13 ms 37976 KB Output is correct
12 Correct 12 ms 38232 KB Output is correct
13 Correct 574 ms 50504 KB Output is correct
14 Correct 609 ms 50520 KB Output is correct
15 Correct 541 ms 50228 KB Output is correct
16 Correct 557 ms 49984 KB Output is correct
17 Correct 629 ms 50120 KB Output is correct
18 Correct 511 ms 51104 KB Output is correct