Submission #447849

#	Time	Username	Problem	Language	Result	Execution time	Memory
447849		Antekb	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	1 ms	332 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N=1<<3;
typedef long long ll;
ll tab[N];
int lew[N+N], pra[N+N];
ll dp[2][2][N+N];
int red(ll a){
	if(a==0)return 0;
	return a/abs(a);
}
void upd(int v){
	if(v>=N){
		dp[0][0][v]=dp[1][0][v]=dp[0][1][v]=0;
		dp[1][1][v]=abs(tab[v-N]);
		return;
	}
	int L=lew[v], R=pra[v], M=(L+R)>>1;
	int l=2*v, r=2*v+1;
	if(red(tab[M])*red(tab[M+1])<0){
		//cout<<v<<"a\n";
		for(int x=0; x<2; x++){
			for(int y=0; y<2; y++){
				dp[x][y][v]=0;
				for(int i=0; i<2; i++){
					for(int j=0; j+i<2; j++){
						dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]);
					}
				}
			}
		}
	}
	else{
		//cout<<v<<"b\n";
		for(int x=0; x<2; x++){
			for(int y=0; y<2; y++){
				dp[x][y][v]=0;
				for(int i=0; i<2; i++){
					for(int j=0; j<2; j++){
						dp[x][y][v]=max(dp[x][y][v], dp[x][i][l]+dp[j][y][r]);
					}
				}
			}
		}
	}
}
void construct(){
	for(int i=N; i<N+N; i++){
		lew[i]=i-N;
		pra[i]=i-N;
		upd(i);
	}
	for(int i=N-1; i>0; i--){
		lew[i]=lew[2*i];
		pra[i]=pra[2*i+1];
		upd(i);
	}
}
int n, q;
void ust(int i, int x){
	if(i==0 || i==n)return;
	tab[i]=x;
	i+=N;
	while(i>0){
		upd(i);
		i/=2;
	}
}
void out(){
	for(int i=0; i<=n; i++)cout<<tab[i]<<" ";
		cout<<"\n";
	for(int i=1; i<N+N; i++){
		cout<<i<<" "<<dp[0][0][i]<<" "<<dp[0][1][i]<<" "<<dp[1][0][i]<<" "<<dp[1][1][i]<<"\n";
	}
	cout<<"\n";
}
int main(){
	cin>>n>>q;
	int p;
	cin>>p;
	for(int i=1; i<n; i++){
		int pp;
		cin>>pp;
		tab[i]=pp-p;
		p=pp;
	}
	construct();
	while(q--){
		int l, r, d;
		cin>>l>>r>>d;
		ust(l-1, tab[l-1]+d);
		ust(r, tab[r]-d);
		//out();
		cout<<max({dp[0][0][1], dp[0][1][1], dp[1][1][1], dp[1][0][1]})<<"\n";
	}
}

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