oj.uz

Submission #670278

# Submission time Handle Problem Language Result Execution time Memory
670278 2022-12-08T14:34:16 Z chanhchuong123 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 481 ms 37708 KB 
#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define ll long long
#define int 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(long long int, long long int, long long int)':
Main.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:83:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   83 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |     ^~
Main.cpp:83:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   83 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |                                                ^~
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".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:73:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |      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 1 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 1 ms 340 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 4 ms 864 KB Output is correct
12 Correct 4 ms 852 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 1 ms 340 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 5 ms 864 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 4 ms 864 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 450 ms 37308 KB Output is correct
14 Correct 451 ms 37152 KB Output is correct
15 Correct 456 ms 37156 KB Output is correct
16 Correct 481 ms 37044 KB Output is correct
17 Correct 447 ms 37040 KB Output is correct
18 Correct 415 ms 37708 KB Output is correct