oj.uz

Submission #643557

# Submission time Handle Problem Language Result Execution time Memory
643557 2022-09-22T12:35:59 Z rsjw Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 910 ms 29488 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 11 ms 676 KB Output is correct
8 Correct 11 ms 732 KB Output is correct
9 Correct 10 ms 724 KB Output is correct
10 Correct 10 ms 716 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 10 ms 736 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 11 ms 676 KB Output is correct
8 Correct 11 ms 732 KB Output is correct
9 Correct 10 ms 724 KB Output is correct
10 Correct 10 ms 716 KB Output is correct
11 Correct 11 ms 724 KB Output is correct
12 Correct 10 ms 736 KB Output is correct
13 Correct 898 ms 28952 KB Output is correct
14 Correct 856 ms 28940 KB Output is correct
15 Correct 834 ms 29032 KB Output is correct
16 Correct 910 ms 28888 KB Output is correct
17 Correct 834 ms 28856 KB Output is correct
18 Correct 824 ms 29488 KB Output is correct