oj.uz

Submission #569049

# Submission time Handle Problem Language Result Execution time Memory
569049 2022-05-26T14:19:45 Z x0r Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 719 ms 28112 KB 
#pragma GCC optimize ("O2")
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first 
#define se second
#define pll pair < ll, ll >
#define pii pair < int, int >
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const string NAME = "";
const string NAME2 = "TEST";
const ll ESP = 1e-9;
const ll INF = 1e18;
const ll nmax = 2e5;
const ll MOD = 1e9 + 7;
const ll base = 2309;

void fre() {
	string finp = NAME + ".inp";
	string fout = NAME + ".out";
	freopen(finp.c_str(), "r", stdin);
	freopen(fout.c_str(), "w", stdout);
}

struct Node {
	ll dp[2][2];
} it[1200003];

ll n, m, a[200003];

Node merge (Node x, Node y, int r) {
	Node res;
	res.dp[0][0] = res.dp[1][1] = res.dp[1][0] = res.dp[0][1] = -INF;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int p = 0; p < 2; p++) {
				for (int q = 0; q < 2; q++) {
					if (p == 1 && q == 1 && a[r] * a[r + 1] < 0) continue;
					res.dp[i][j] = max(res.dp[i][j], x.dp[i][p] + y.dp[q][j]);
				}
			}
		}	
	}
	return res;
}

void build_tree(int node, int l, int r) {
	//cout << node << " " << l << " " << r << '\n';
	if (l == r) {
		it[node].dp[0][1] = it[node].dp[1][0] = -INF;
		it[node].dp[1][1] = abs(a[l]);
		it[node].dp[0][0] = 0;
		//cout << l << " " << r << " " << max(it[node].dp[0][0], max(it[node].dp[0][1], max(it[node].dp[1][0], it[node].dp[1][1]))) << '\n';
		return ;
	}
	build_tree(node * 2, l, (l + r) / 2);
	build_tree(node * 2 + 1, (l + r) / 2 + 1, r);
	it[node] = merge(it[node * 2], it[node * 2 + 1], (l + r) / 2);
	//cout << l << " " << r << " " << max(it[node].dp[0][0], max(it[node].dp[0][1], max(it[node].dp[1][0], it[node].dp[1][1]))) << '\n';

}

void update(int node, int l, int r, int pos) {
	if (pos < l || pos > r) return ;
	if (l == r) {
		it[node].dp[0][1] = it[node].dp[1][0] = -INF;
		it[node].dp[1][1] = abs(a[l]);
		it[node].dp[0][0] = 0;
		return ;
	}
	update(node * 2, l, (l + r) / 2, pos);
	update(node * 2 + 1, (l + r) / 2 + 1, r, pos);
	it[node] = merge(it[node * 2], it[node * 2 + 1], (l + r) / 2);
}

void sol() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i < n; i++) a[i] = a[i] - a[i + 1];
	n--;
	build_tree(1, 1, n);
	//cout << max(it[1].dp[0][0], max(it[1].dp[0][1], max(it[1].dp[1][0], it[1].dp[1][1]))) << '\n';
	while (m--) {
		ll l, r, x;
		cin >> l >> r >> x;
		if (l != 1) a[l - 1] -= x;
		a[r] += x;
		update(1, 1, n, l - 1);
		update(1, 1, n, r);
		cout << max(it[1].dp[0][0], max(it[1].dp[0][1], max(it[1].dp[1][0], it[1].dp[1][1]))) << '\n';

	}
}

int main() {
	fast;
	//fre();
	int t = 1;
	//cin >> t;
	while (t --) sol();
}

Compilation message

Main.cpp: In function 'void fre()':
Main.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen(finp.c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen(fout.c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 7 ms 812 KB Output is correct
9 Correct 6 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 7 ms 728 KB Output is correct
12 Correct 6 ms 724 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 7 ms 724 KB Output is correct
8 Correct 7 ms 812 KB Output is correct
9 Correct 6 ms 724 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 7 ms 728 KB Output is correct
12 Correct 6 ms 724 KB Output is correct
13 Correct 660 ms 27388 KB Output is correct
14 Correct 719 ms 27492 KB Output is correct
15 Correct 691 ms 27460 KB Output is correct
16 Correct 619 ms 27364 KB Output is correct
17 Correct 658 ms 27184 KB Output is correct
18 Correct 692 ms 28112 KB Output is correct