oj.uz

답안 #417394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417394 2021-06-03T16:14:04 Z rqi Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 339892 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1322 ms 332800 KB Output is correct
2 Correct 1305 ms 332812 KB Output is correct
3 Correct 1292 ms 332796 KB Output is correct
4 Correct 1330 ms 332740 KB Output is correct
5 Correct 1311 ms 332736 KB Output is correct
6 Correct 1280 ms 332740 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1322 ms 332800 KB Output is correct
2 Correct 1305 ms 332812 KB Output is correct
3 Correct 1292 ms 332796 KB Output is correct
4 Correct 1330 ms 332740 KB Output is correct
5 Correct 1311 ms 332736 KB Output is correct
6 Correct 1280 ms 332740 KB Output is correct
7 Correct 1594 ms 332920 KB Output is correct
8 Correct 1563 ms 333008 KB Output is correct
9 Correct 1593 ms 332996 KB Output is correct
10 Correct 1577 ms 332960 KB Output is correct
11 Correct 1614 ms 332928 KB Output is correct
12 Correct 1608 ms 333052 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1322 ms 332800 KB Output is correct
2 Correct 1305 ms 332812 KB Output is correct
3 Correct 1292 ms 332796 KB Output is correct
4 Correct 1330 ms 332740 KB Output is correct
5 Correct 1311 ms 332736 KB Output is correct
6 Correct 1280 ms 332740 KB Output is correct
7 Correct 1594 ms 332920 KB Output is correct
8 Correct 1563 ms 333008 KB Output is correct
9 Correct 1593 ms 332996 KB Output is correct
10 Correct 1577 ms 332960 KB Output is correct
11 Correct 1614 ms 332928 KB Output is correct
12 Correct 1608 ms 333052 KB Output is correct
13 Execution timed out 2095 ms 339892 KB Time limit exceeded
14 Halted 0 ms 0 KB -