Submission #442023

#	Time	Username	Problem	Language	Result	Execution time	Memory
442023		keta_tsimakuridze	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1547 ms	22940 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N][2][2],a[N],x[N],n,q;
void update(int u,int ind,int l,int r,int val) {
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u][0][0] = 0;
		tree[u][1][1] = abs(val);
		return;
	}
	int mid = (l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	for(int i=0;i<2;i++) {
		for(int j=0;j<2;j++){ tree[u][i][j] = 0;
			for(int k=0;k<2;k++) {
				for(int c=0;c<2;c++) {	
					if(k==1 && c==1 && min(x[mid],x[mid+1])<0 && max(x[mid],x[mid+1])>0)  {
						continue;
					}
					tree[u][i][j] = max(tree[2*u][i][k] + tree[2*u+1][c][j], tree[u][i][j]);
				}
			}
		}
	} 
}
 main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin >> a[i];
		x[i] = a[i] - a[i-1];
		if(i-1) update(1,i,1,n,a[i]-a[i-1]);
		
	
	} 
	while(q--) {
		int l,r,val;
		cin>>l>>r>>val;
		x[l] += val;
		x[r+1] += -val; 
		if(l-1) update(1,l,1,n,x[l]);
		update(1,r+1,1,n,x[r+1]);
		cout<<max(max(tree[1][1][1],tree[1][0][0]),max(tree[1][1][0],tree[1][0][1]))<<endl;
	}
}

Compilation message (stderr)

Main.cpp:31:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 |  main(){
      |  ^~~~

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