Submission #643557

#	Time	Username	Problem	Language	Result	Execution time	Memory
643557		rsjw	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	910 ms	29488 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 800010;
int arr[N],a[N];
int n;

int sum[N][2][2];
void chmax(int &var,int v) {
	if(v>var) var=v;
}
void pushup(int rt,bool mixable){
	int i,j,_i,_j;
	for(i=0;i<2;i++) {
		for(j=0;j<2;j++) {
			sum[rt][i][j]=0;
			for(_i=0;_i<2;_i++) {
				for(_j=0;_j<2;_j++) {
					if(_i&&_j&&0==mixable) continue;
					chmax(sum[rt][i][j],sum[rt<<1][i][_i]+sum[rt<<1|1][_j][j]);
				}
			}		
		}
	}
}
void build(int l=1,int r=n,int rt=1) {
	if(l==r) {
		sum[rt][1][1]=abs(a[l]);
		return ;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	pushup(rt,a[m]*a[m+1]>=0);
}
void update(int x,int I,int l=1,int r=n,int rt=1) {
	if(l==r) {
		sum[rt][1][1]=abs(I);
		return ;
	}
	int m=(l+r)>>1;
	if(x<=m) update(x,I,l,m,rt<<1);
	else update(x,I,m+1,r,rt<<1|1);
	pushup(rt,a[m]*a[m+1]>=0);
}
signed main() {
	//freopen("1.in","r",stdin);
	int q,i,l,r,x;
	cin>>n>>q;
	for(i=1;i<=n;i++) cin>>arr[i];
	for(i=1;i<n;i++) a[i]=arr[i+1]-arr[i];
	n--;
	build();
	int j,_i,_j,ans=0;
	while(q--) {
		cin>>l>>r>>x;
		if(l-1>0) {
			a[l-1]+=x;
			update(l-1,a[l-1]);
		}
		if(r<=n) {
			a[r]-=x;
			update(r,a[r]);
		}
		ans=0;
		for(i=0;i<2;i++)
			for(j=0;j<2;j++) 
				ans=max(ans,sum[1][i][j]);
		cout<<ans<<endl;
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:8: warning: unused variable '_i' [-Wunused-variable]
   54 |  int j,_i,_j,ans=0;
      |        ^~
Main.cpp:54:11: warning: unused variable '_j' [-Wunused-variable]
   54 |  int j,_i,_j,ans=0;
      |           ^~

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