Submission #1113472

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113472		LM1	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	281 ms	31304 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define TREE int st,int l,int r
#define left st*2,l,(l+r)/2
#define right st*2+1,(l+r)/2+1,r
const int N=2e5+5;
int ind,a[N],n,q;
ll t[4*N][2][2],b[N],ans;
void update(TREE){
	if(r<ind or l>ind)return;
	if(l==r){
		t[st][1][1]=abs(b[ind]);
		return;
	}
	int mid=(l+r)/2,x=st*2,y=st*2+1;
	update(left);update(right);
	if((b[mid]>=0 and b[mid+1]>=0) or (b[mid]<=0 and b[mid+1]<=0)){
		t[st][0][1]=max(t[x][0][1],t[x][0][0])+max(t[y][0][1],t[y][1][1]);
		t[st][1][0]=max(t[x][1][1],t[x][1][0])+max(t[y][0][0],t[y][1][0]);
		t[st][0][0]=max(t[x][0][0],t[x][0][1])+max(t[y][0][0],t[y][1][0]);
		t[st][1][1]=max(t[x][1][0],t[x][1][1])+max(t[y][0][1],t[y][1][1]);
	}
	else{
		t[st][0][1]=max(t[x][0][0]+t[y][1][1],t[x][0][1]+t[y][0][1]);
		t[st][1][0]=max(t[x][1][0]+t[y][1][0],t[x][1][1]+t[y][0][0]);
		t[st][0][0]=max(t[x][0][0]+t[y][1][0],t[x][0][1]+t[y][0][0]);
		t[st][1][1]=max(t[x][1][0]+t[y][1][1],t[x][1][1]+t[y][0][1]);
	}
}
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i>0){
			b[i]=a[i]-a[i-1];
			ind=i;
			update(1,1,n-1);
		}
	}
	while(q--){
		int l,r,x;cin>>l>>r>>x;
		if(l-1>=1){
			b[l-1]+=x;
			ind=l-1;
			update(1,1,n-1);
		}
		if(r<n){
			b[r]-=x;
			ind=r;
			update(1,1,n-1);
		}
		ans=max(t[1][0][0],t[1][0][1]);
		ans=max(ans,t[1][1][0]);
		ans=max(ans,t[1][1][1]);
		cout<<ans<<"\n";
		//b[r]=a[r+1]-a[r]
		//b[l]=a[l+1]-a[l]
	}
}
/*
3 5 8 6 4 10 12= 9
3 5 8 | 6 | 4 10 12=13
x    a,b         y =y-x
b<a
a-x+y-b=y-x+a-b

3 5 | 8 6 | 4 10 12  =2+2+8=12

3 5 8 6 10 12=9
3 5 8 | 6 10 12=5+6=11

12 - 3
8-3+12-6=12-3 +8-6

dpkl[i]=dpkl[i-1]+1
b[i]<0
+=x
b[i]>=0
dpkl[i-1]
dpkl[i-n]--

int st,x=st*2,y=st*2+1;
if((b[mid]>=0 and b[mid+1]>=0) or (b[mid]<=0 and b[mid+1]<=0)){
	t[st][0][1]=max(t[x][0][1],t[x][0][0])+max(t[y][0][1],t[y][1][1]);
	t[st][1][0]=max(t[x][1][1],t[x][1][0])+max(t[y][0][0],t[y][1][0]);
	t[st][0][0]=max(t[x][0][0],t[x][0][1])+max(t[y][0][0],t[y][1][0]);
	t[st][1][1]=max(t[x][1][0],t[x][1][1])+max(t[y][0][1],t[y][1][1]);
}
t[st][0][1]=max(t[x][0][0]+t[y][1][1],t[x][0][1]+t[y][0][1]);
t[st][1][0]=max(t[x][1][0]+t[y][1][0],t[x][1][1]+t[y][0][0]);
t[st][0][0]=max(t[x][0][0]+t[y][1][0],t[x][0][1]+t[y][0][0]);
t[st][1][1]=max(t[x][1][0]+t[y][1][1],t[x][1][1]+t[y][0][1]);
*/

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