제출 #417394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417394		rqi	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	2095 ms	339892 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;
	map<pi, ll> 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[mp(i, j)] = -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[mp(i, j)] = -INF;
					continue;
				}
				int typ = i;
				if(typ == 0) typ = j;
				if(typ == -1){
					dp[mp(i, j)] = -v;
				}
				else if(typ == 0){
					dp[mp(i, j)] = 0;
				}
				else{
					dp[mp(i, j)] = 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[mp(i, j)], res.max_val-res.min_val);
			}
			else if(zero_num == 1){
				if(typ == 1){
					ckmax(res.dp[mp(i, j)], res.max_val);
				}
				else if(typ == -1){
					ckmax(res.dp[mp(i, j)], -res.min_val);
				}
			}

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

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

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

	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(auto& u: Seg[ind].dp){
		int sum = u.f.f+u.f.s;
		u.s+=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[mp(0, 0)] << "\n";
	}
}

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