oj.uz

Submission #1011700

# Submission time Handle Problem Language Result Execution time Memory
1011700 2024-07-01T06:48:24 Z pcc Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 771 ms 64848 KB 
#include <bits/stdc++.h>
using namespace std;


#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define pii pair<int,int>

const int mxn = 2e5+10;
const ll inf = 1e18;
ll arr[mxn];
int N,Q;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	struct node{
		ll dp[3][3];
		node(){
			for(auto &i:dp)for(auto &j:i)j = -inf;
		}
	};
	node seg[mxn*4];
	node pull(node pl,node pr){
		node re = node();
		for(int i = 0;i<=2;i++){
			for(int j = 0;j<=2;j++){
				for(int k = 0;k<=2;k++){
					re.dp[i][j] = max({re.dp[i][j],pl.dp[i][0]+pr.dp[k][j],pl.dp[i][k]+pr.dp[0][j]});
					re.dp[i][j] = max({re.dp[i][j],pl.dp[i][k]+pr.dp[k][j]});
				}
			}
		}
		return re;
	}
	void modify(int now,int l,int r,int p,ll v){
		if(l == r){
			for(auto &i:seg[now].dp)for(auto &j:i)j = -inf;
			seg[now].dp[1][1] = v;
			seg[now].dp[2][2] = -v;
			seg[now].dp[0][0] = 0;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	SEG(){}
#undef ls
#undef rs
#undef mid
};

SEG seg;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	for(int i = N;i>=2;i--){
		arr[i] -= arr[i-1];
		seg.modify(0,2,N,i,arr[i]);
	}

	while(Q--){
		int s,e,v;
		cin>>s>>e>>v;
		arr[s] += v;
		arr[e+1] -= v;
		if(s>1&&s<=N)seg.modify(0,2,N,s,arr[s]);
		if(e+1<=N)seg.modify(0,2,N,e+1,arr[e+1]);
		auto re = seg.seg[0].dp;
		ll ans = 0;
		for(int i = 0;i<3;i++)for(int j = 0;j<3;j++)ans = max(ans,re[i][j]);
		cout<<ans<<'\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56668 KB Output is correct
2 Correct 13 ms 56668 KB Output is correct
3 Correct 14 ms 56668 KB Output is correct
4 Correct 16 ms 56668 KB Output is correct
5 Correct 13 ms 56668 KB Output is correct
6 Correct 14 ms 56740 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56668 KB Output is correct
2 Correct 13 ms 56668 KB Output is correct
3 Correct 14 ms 56668 KB Output is correct
4 Correct 16 ms 56668 KB Output is correct
5 Correct 13 ms 56668 KB Output is correct
6 Correct 14 ms 56740 KB Output is correct
7 Correct 20 ms 56920 KB Output is correct
8 Correct 26 ms 56924 KB Output is correct
9 Correct 20 ms 56920 KB Output is correct
10 Correct 21 ms 56924 KB Output is correct
11 Correct 20 ms 56924 KB Output is correct
12 Correct 20 ms 56920 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 56668 KB Output is correct
2 Correct 13 ms 56668 KB Output is correct
3 Correct 14 ms 56668 KB Output is correct
4 Correct 16 ms 56668 KB Output is correct
5 Correct 13 ms 56668 KB Output is correct
6 Correct 14 ms 56740 KB Output is correct
7 Correct 20 ms 56920 KB Output is correct
8 Correct 26 ms 56924 KB Output is correct
9 Correct 20 ms 56920 KB Output is correct
10 Correct 21 ms 56924 KB Output is correct
11 Correct 20 ms 56924 KB Output is correct
12 Correct 20 ms 56920 KB Output is correct
13 Correct 728 ms 64380 KB Output is correct
14 Correct 771 ms 64412 KB Output is correct
15 Correct 702 ms 64592 KB Output is correct
16 Correct 771 ms 64400 KB Output is correct
17 Correct 709 ms 64328 KB Output is correct
18 Correct 747 ms 64848 KB Output is correct