oj.uz

Submission #670279

# Submission time Handle Problem Language Result Execution time Memory
670279 2022-12-08T14:34:57 Z chanhchuong123 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 464 ms 26316 KB 
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 2e5 + 3;
int n, q, a[N]; ll d[N];

struct node {
	int L, R;
	ll dp[2][2];
} st[N << 2];

void combine(int id, bool ok) {
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			st[id].dp[i][j] = 0;
			for (int _i = 0; _i < 2; _i++) {
				for (int _j = 0; _j < 2; _j++) {
					if (_i && _j && ok == false) continue;
					maxi(st[id].dp[i][j], st[id << 1].dp[i][_i] + st[id << 1 | 1].dp[_j][j]);
				}
			}
		}
	}
}

void build(int id, int l, int r) {
	if (l == r) {
		st[id].L = st[id].R = l;
		st[id].dp[0][0] = 0;
		st[id].dp[0][1] = 0;
		st[id].dp[1][0] = 0;
		st[id].dp[1][1] = abs(d[l]);
	} else {
		int mid = l + r >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		combine(id, 1LL * d[mid] * d[mid + 1] >= 0);
	}
}

void update(int id, int l, int r, int pos, int delta) {
	if (l == r) {
		d[l] += delta; //cout << d[l] << '\n';
		st[id].dp[1][1] = abs(d[l]);
	} else {
		int mid = l + r >> 1;
		if (pos <= mid) update(id << 1, l, mid, pos, delta);
		else update(id << 1 | 1, mid + 1, r, pos, delta);
		combine(id, 1LL * d[mid] * d[mid + 1] >= 0);
	}
}

int32_t main() {
  	ios_base::sync_with_stdio(0);
  	cin.tie(0); cout.tie(0);

  	if (fopen(task".inp","r")) {
    	freopen(task".inp","r",stdin);
    	freopen(task".out","w",stdout);
  	}

  	cin >> n >> q;
  	for (int i = 1; i <= n; i++) cin >> a[i];
  	for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];

  	build(1, 1, n - 1);
  	while (q--) {
  		int l, r, x; cin >> l >> r >> x;
  		if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
  		cout << max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]}) << '\n';
  	}
}

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:82:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |     ^~
Main.cpp:82:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |                                                ^~
Main.cpp:71:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:72:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |      freopen(task".out","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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 4 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 449 ms 25904 KB Output is correct
14 Correct 464 ms 25988 KB Output is correct
15 Correct 449 ms 26072 KB Output is correct
16 Correct 451 ms 26060 KB Output is correct
17 Correct 447 ms 25932 KB Output is correct
18 Correct 403 ms 26316 KB Output is correct