oj.uz

Submission #417401

# Submission time Handle Problem Language Result Execution time Memory
417401 2021-06-03T16:20:47 Z rqi Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1615 ms 64032 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;
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49604 KB Output is correct
2 Correct 48 ms 49568 KB Output is correct
3 Correct 49 ms 49604 KB Output is correct
4 Correct 49 ms 49548 KB Output is correct
5 Correct 49 ms 49556 KB Output is correct
6 Correct 52 ms 49604 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49604 KB Output is correct
2 Correct 48 ms 49568 KB Output is correct
3 Correct 49 ms 49604 KB Output is correct
4 Correct 49 ms 49548 KB Output is correct
5 Correct 49 ms 49556 KB Output is correct
6 Correct 52 ms 49604 KB Output is correct
7 Correct 67 ms 49672 KB Output is correct
8 Correct 65 ms 49580 KB Output is correct
9 Correct 64 ms 49604 KB Output is correct
10 Correct 66 ms 49604 KB Output is correct
11 Correct 65 ms 49596 KB Output is correct
12 Correct 66 ms 49696 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49604 KB Output is correct
2 Correct 48 ms 49568 KB Output is correct
3 Correct 49 ms 49604 KB Output is correct
4 Correct 49 ms 49548 KB Output is correct
5 Correct 49 ms 49556 KB Output is correct
6 Correct 52 ms 49604 KB Output is correct
7 Correct 67 ms 49672 KB Output is correct
8 Correct 65 ms 49580 KB Output is correct
9 Correct 64 ms 49604 KB Output is correct
10 Correct 66 ms 49604 KB Output is correct
11 Correct 65 ms 49596 KB Output is correct
12 Correct 66 ms 49696 KB Output is correct
13 Correct 1615 ms 61140 KB Output is correct
14 Correct 1534 ms 63384 KB Output is correct
15 Correct 1537 ms 63420 KB Output is correct
16 Correct 1525 ms 63320 KB Output is correct
17 Correct 1564 ms 63172 KB Output is correct
18 Correct 1584 ms 64032 KB Output is correct