Submission #417401

#	Time	Username	Problem	Language	Result	Execution time	Memory
417401		rqi	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1615 ms	64032 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

#define f first
#define s second
#define mp make_pair

const ll INF = ll(1e18);

void ckmax(ll& a, ll b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a ,b);
}

struct node{
	ll max_val, min_val;
	array<array<ll, 3>, 3> dp;
	bool id;
	node(){
		max_val = -INF;
		min_val = INF;
		for(int i = -1; i <= 1; i++){
			for(int j = -1; j <= 1; j++){
				dp[i+1][j+1] = -INF;
			}
		}
		id = 0;
	}

	node(ll v){
		max_val = min_val = v;
		for(int i = -1; i <= 1; i++){
			for(int j = -1; j <= 1; j++){
				int zero_num = 0;
				if(i == 0) zero_num++;
				if(j == 0) zero_num++;
				if(zero_num == 0){
					dp[i+1][j+1] = -INF;
					continue;
				}
				int typ = i;
				if(typ == 0) typ = j;
				if(typ == -1){
					dp[i+1][j+1] = -v;
				}
				else if(typ == 0){
					dp[i+1][j+1] = 0;
				}
				else{
					dp[i+1][j+1] = v;
				}
			}
		}
		id = 0;
	}
};

node ID;

node comb(node a, node b){
	if(a.id) return b;
	if(b.id) return a;
	node res = node();
	res.max_val = max(a.max_val, b.max_val);
	res.min_val = min(a.min_val, b.min_val);
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
			int zero_num = 0;
			if(i == 0) zero_num++;
			if(j == 0) zero_num++;
			int typ = i;
			if(typ == 0) typ = j;

			if(typ == 0){
				ckmax(res.dp[i+1][j+1], res.max_val-res.min_val);
			}
			else if(zero_num == 1){
				if(typ == 1){
					ckmax(res.dp[i+1][j+1], res.max_val);
				}
				else if(typ == -1){
					ckmax(res.dp[i+1][j+1], -res.min_val);
				}
			}

			ckmax(res.dp[i+1][j+1], a.dp[i+1][0+1]+b.dp[0+1][j+1]);	
			ckmax(res.dp[i+1][j+1], a.dp[i+1][j+1]);
			ckmax(res.dp[i+1][j+1], b.dp[i+1][j+1]);

			if(i == 0){
				ckmax(res.dp[i+1][j+1], a.max_val+b.dp[-1+1][j+1]);
				ckmax(res.dp[i+1][j+1], -a.min_val+b.dp[1+1][j+1]);
			}
			if(j == 0){
				ckmax(res.dp[i+1][j+1], a.dp[i+1][-1+1]+b.max_val);
				ckmax(res.dp[i+1][j+1], a.dp[i+1][1+1]-b.min_val);
			}

			ckmax(res.dp[i+1][j+1], a.dp[i+1][-1+1]+b.dp[1+1][j+1]);
			ckmax(res.dp[i+1][j+1], a.dp[i+1][1+1]+b.dp[-1+1][j+1]);
		}
	}

	return res;
}

const int mx = 200005;
const int SZ = 262144;
int n, q;
node Seg[2*SZ];
ll lazy[2*SZ];

ll a[mx];

void push(int ind){
	Seg[ind].max_val+=lazy[ind];
	Seg[ind].min_val+=lazy[ind];
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
			int sum = i+j;
			Seg[ind].dp[i+1][j+1]+=ll(lazy[ind])*sum;
		}
	}

	for(int i = 0; i < 2; i++){
		if(2*ind+i < 2*SZ){
			lazy[2*ind+i]+=lazy[ind];
		}
	}
	lazy[ind] = 0;
}

void pull(int ind){
	assert(2*ind+1 < 2*SZ);
	Seg[ind] = comb(Seg[2*ind], Seg[2*ind+1]);
}

void upd(int lo, int hi, ll val, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);
	if(R < lo || hi < L) return;

	if(lo <= L && R <= hi){
		lazy[ind]+=val;
		push(ind);
		return;
	}

	int M = (L+R)/2;
	upd(lo, hi, val, 2*ind, L, M);
	upd(lo, hi, val, 2*ind+1, M+1, R);
	pull(ind);
}

node query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1){
	push(ind);
	if(R < lo || hi < L) return ID;
	if(lo <= L && R <= hi){
		node res = Seg[ind];
		return res;
	}
	int M = (L+R)/2;
	return comb(query(lo, hi, 2*ind, L, M), query(lo, hi, 2*ind+1, M+1, R));
}

void build(){
	for(int i = 0; i < n; i++){
		Seg[SZ+i] = node(a[i+1]);
	}
	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	ID.id = 1;
	
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	build();


	// for(auto u: Seg[SZ].dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }
	// for(auto u: Seg[SZ+1].dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }
	// for(auto u: Seg[SZ/2].dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }
	// for(auto u: Seg[(SZ+2)/2].dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }

	// for(auto u: Seg[SZ/4].dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }

	// node TOP = query(0, n-1);
	// for(auto u: TOP.dp){
	// 	cout << u.f.f << " " << u.f.s << ": " << u.s << "\n";
	// }

	for(int i = 1; i <= q; i++){
		int l, r;
		ll x;
		cin >> l >> r >> x;
		upd(l-1, r-1, x);
		node res = query(0, n-1);
		cout << res.dp[0+1][0+1] << "\n";
	}
}

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