oj.uz

Submission #985261

# Submission time Handle Problem Language Result Execution time Memory
985261 2024-05-17T13:57:55 Z michified Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 604 ms 61732 KB 
#include <bits/stdc++.h>
#define ll long long
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;

struct node_t {
	ll nlnr, nlyr, ylnr, ylyr, l, r;
};

int n, q;
vector<node_t> st;
vector<ll> d;

node_t merge(node_t& a, node_t& b) {
	node_t res;
	bool can = (a.r >= 0 and b.l >= 0) or (a.r <= 0 and b.l <= 0);
	res.nlnr = max(max(a.nlyr + b.nlnr, a.nlnr + b.nlnr), 
			   max(a.nlnr + b.ylnr, can ? a.nlyr + b.ylnr : -1));
	res.ylnr = max(max(a.ylyr + b.nlnr, a.ylnr + b.nlnr), 
			   max(a.ylnr + b.ylnr, can ? a.ylyr + b.ylnr : -1));
	res.nlyr = max(max(a.nlyr + b.nlyr, a.nlnr + b.nlyr), 
			   max(a.nlnr + b.ylyr, can ? a.nlyr + b.ylyr : -1));
	res.ylyr = max(max(a.ylyr + b.nlyr, a.ylnr + b.nlyr), 
			   max(a.ylnr + b.ylyr, can ? a.ylyr + b.ylyr : -1));
	res.l = a.l;
	res.r = b.r;
	return res;
}

void build(int id, int l, int r) {
	if (l == r) {
		st[id] = {0, 0, 0, abs(d[l]), d[l], d[l]};
		return;
	}
	int mid = (l + r) / 2;
	build(lid, l, mid);
	build(rid, mid + 1, r);
	st[id] = merge(st[lid], st[rid]);
}

void upd(int id, int l, int r, int i, int val) {
	if (l == r) {
		d[l] += val;
		st[id] = {0, 0, 0, abs(d[l]), d[l], d[l]};
		return;
	}
	int mid = (l + r) / 2;
	if (i <= mid) upd(lid, l, mid, i, val);
	else upd(rid, mid + 1, r, i, val);
	st[id] = merge(st[lid], st[rid]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> q;
	int i, m;
	vector<ll> a(n);
	for (i = 0; i < n; i++) cin >> a[i];
	m = n - 1;
	d.resize(m);
	st.resize(m * 4);
	for (i = 0; i < m; i++) d[i] = a[i + 1] - a[i];
	build(0, 0, m - 1);
	vector<vector<int>> ques(q, vector<int>(3));
	for (i = 0; i < q; i++) cin >> ques[i][0] >> ques[i][1] >> ques[i][2];
	for (auto& que : ques) {
		if (que[0] > 1) upd(0, 0, m - 1, que[0] - 2, que[2]);
		if (que[1] < n) upd(0, 0, m - 1, que[1] - 1, -que[2]);
		cout << st[0].ylyr << endl;
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 1372 KB Output is correct
8 Correct 7 ms 1344 KB Output is correct
9 Correct 7 ms 1116 KB Output is correct
10 Correct 7 ms 1112 KB Output is correct
11 Correct 7 ms 1332 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 1372 KB Output is correct
8 Correct 7 ms 1344 KB Output is correct
9 Correct 7 ms 1116 KB Output is correct
10 Correct 7 ms 1112 KB Output is correct
11 Correct 7 ms 1332 KB Output is correct
12 Correct 7 ms 1372 KB Output is correct
13 Correct 580 ms 61132 KB Output is correct
14 Correct 604 ms 61104 KB Output is correct
15 Correct 603 ms 61104 KB Output is correct
16 Correct 594 ms 61120 KB Output is correct
17 Correct 559 ms 61080 KB Output is correct
18 Correct 562 ms 61732 KB Output is correct