Submission #366334

#	Time	Username	Problem	Language	Result	Execution time	Memory
366334		kshitij_sodani	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1068 ms	46220 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n,q;
llo it[200001];
llo dp[200001];
llo tree[200001*4][3][3];//(left negative,left empty,left positive)
llo lazy[200001*4];
void push(llo no,llo l,llo r){
	for(llo i=0;i<3;i++){
		for(llo j=0;j<3;j++){
			tree[no][i][j]+=(lazy[no]*(i-1+j-1));
		}
	}
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	//	lazy[no]=0;		
	}
	lazy[no]=0;
}

//pair<llo,llo> tree[200001*4][3][3];
void build(llo no,llo l,llo r){
	if(l==r){
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				tree[no][i][j]=-1e17;
			}
		}
		tree[no][1][1]=0;
		for(llo i=0;i<3;i+=2){
			tree[no][i][1]=(i-1)*it[l];
			tree[no][1][i]=(i-1)*it[l];
		}
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				tree[no][i][j]=max(tree[no*2+1][i][j],tree[no*2+2][i][j]);
			}
		}
		
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j+=2){
				for(llo k=0;k<3;k+=2){
					for(llo l=0;l<3;l++){
						if(j!=k){
							tree[no][i][l]=max(tree[no][i][l],tree[no*2+1][i][j]+tree[no*2+2][k][l]);
						}
					}
				}
			}
		}
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				tree[no][i][j]=max(tree[no*2+1][i][1]+tree[no*2+2][1][j],tree[no][i][j]);
				
			}
		}
		

	}
/*
			cout<<l<<":"<<r<<endl;
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				cout<<tree[no][i][j]<<",";
			}
			cout<<endl;
		}
*/
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
	push(no,l,r);
	if(r<aa or l>bb){
		return;
	}
	if(aa<=l and r<=bb){
		lazy[no]+=val;
		push(no,l,r);
	}
	else{
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb,val);
		update(no*2+2,mid+1,r,aa,bb,val);
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				tree[no][i][j]=max(tree[no*2+1][i][j],tree[no*2+2][i][j]);

			}
		}
		
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j+=2){
				for(llo k=0;k<3;k+=2){
					for(llo l=0;l<3;l++){
						if(j!=k){
							tree[no][i][l]=max(tree[no][i][l],tree[no*2+1][i][j]+tree[no*2+2][k][l]);
						}
					}
				}
			}
		}
		for(llo i=0;i<3;i++){
			for(llo j=0;j<3;j++){
				tree[no][i][j]=max(tree[no*2+1][i][1]+tree[no*2+2][1][j],tree[no][i][j]);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>q;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	build(0,0,n-1);
	//cout<<tree[0][1][1]<<endl;
	for(llo ii=0;ii<q;ii++){
		llo l,r,aa;
		cin>>l>>r>>aa;

		l--;
		r--;
		update(0,0,n-1,l,r,aa);
		cout<<tree[0][1][1]<<endl;
/*		for(llo j=l-1;j<=r-1;j++){
			it[j]+=aa;
		}

		llo xx=-1e18;
		llo yy=-1e18;
		for(llo i=1;i<=n;i++){
			llo ma=-1e18;
			llo mi=1e18;
			dp[i]=0;
			xx=max(xx,dp[i-1]+it[i-1]);
			yy=max(yy,dp[i-1]-it[i-1]);
			dp[i]=max(dp[i],dp[i-1]);
			dp[i]=max(dp[i],max(xx-it[i-1],yy+it[i-1]));

			

			//cout<<dp[i]<<",";
		}
		//cout<<endl;
		cout<<dp[n]<<endl;*/
	}








 
	return 0;
}

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