Submission #670278

#	Time	Username	Problem	Language	Result	Execution time	Memory
670278		chanhchuong123	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	481 ms	37708 KiB

Main

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55