Submission #1291101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291101		SmuggingSpun	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	387 ms	42540 KiB

Main

#include<bits/stdc++.h>
#define taskname "E"
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
struct Node{
	ll bor[2], dp[2][2];
	Node(){
		memset(dp, 0, sizeof(dp));
	}
	Node(ll v){
		dp[1][1] = abs(bor[0] = bor[1] = v);
		dp[0][0] = dp[0][1] = dp[1][0] = 0;
	}
};
Node merge(Node a, Node b){
	Node c;
	c.bor[0] = a.bor[0];
	c.bor[1] = b.bor[1];
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++){
				for(int l = 0; l < 2; l++){
					if(j == 0 || k == 0 || (a.bor[1] < 0) == (b.bor[0] < 0)){
						maximize(c.dp[i][l], a.dp[i][j] + b.dp[k][l]);
					}
				}
			}
		}
	}
	return c;
}
const int lim = 2e5 + 5;
Node st[lim << 2];
void update(int id, int l, int r, int p, int x){
	if(l == r){
		st[id].bor[0] += x;
		st[id].dp[1][1] = abs(st[id].bor[1] += x);
		return;
	}
	int m = (l + r) >> 1;
	if(m < p){
		update(id << 1 | 1, m + 1, r, p, x);
	}
	else{
		update(id << 1, l, m, p, x);
	}
	st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
int n, q, d[lim];
void build(int id, int l, int r){
	if(l == r){
		st[id] = Node(d[l]);
		return;
	}	
	int m = (l + r) >> 1;
	build(id << 1, l, m);
	build(id << 1 | 1, m + 1, r);
	st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> q;
	vector<int>a(n + 1);
	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);
	for(int _ = 0; _ < 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 << st[1].dp[1][1] << "\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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