Submission #670275

#	Time	Username	Problem	Language	Result	Execution time	Memory
670275		chanhchuong123	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	340 KiB

Main

#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];

node combine(node l, node r) {
	node ans;
	ans.L = l.L; ans.R = r.R;
	ans.dp[0][0] = max({l.dp[0][0] + r.dp[0][0], l.dp[0][0] + r.dp[1][0], l.dp[0][1] + r.dp[0][0], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[0][1] + r.dp[1][0])});
	ans.dp[0][1] = max({l.dp[0][0] + r.dp[0][1], l.dp[0][0] + r.dp[1][1], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[0][1] + r.dp[1][1])});
	ans.dp[1][0] = max({l.dp[1][0] + r.dp[0][0], l.dp[1][0] + r.dp[1][0], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[1][1] + r.dp[1][0])});
	ans.dp[1][1] = max({l.dp[1][0] + r.dp[0][1], l.dp[1][1] + r.dp[0][1], l.dp[1][0] + r.dp[1][1], (1LL * d[l.R] * d[r.L] >= 0) * (l.dp[1][1] + r.dp[1][1])});
	return ans;
}

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);
		st[id] = combine(st[id << 1], st[id << 1 | 1]);
	}
}

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);
		st[id] = combine(st[id << 1], st[id << 1 | 1]);
	}
}

int 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(int, int, int)':
Main.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:78:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   78 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |     ^~
Main.cpp:78:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   78 |     if (l > 1) update(1, 1, n - 1, l - 1, +x); if (r < n) update(1, 1, n - 1, r, -x);
      |                                                ^~
Main.cpp:67:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:68:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55