oj.uz

Submission #993050

# Submission time Handle Problem Language Result Execution time Memory
993050 2024-06-05T09:18:47 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 316 ms 26964 KB 
#include <bits/stdc++.h>
#define int long long 
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int> 

using namespace std;

int a[200005], p[200005];
struct ha{
	int oo , ox , xo , xx;
	void mix(ha& a , ha& b, int mid , int l , int r){
		oo = max({a.ox+b.xo , a.ox+b.oo , a.oo+b.xo});
		ox = max({a.ox+b.ox , a.oo+b.xx , a.ox+b.xx});
		xo = max({a.xx+b.xo , a.xx+b.oo , a.xo+b.xo });
		xx = max({a.xx+b.xx , a.xo+b.xx , a.xo +b.xx , a.xx+b.ox});
		if(((p[mid]>= 0 && p[mid+1]>=0) || (p[mid]<= 0 && p[mid+1] <= 0))){
			
			oo = max({oo , a.ox +b.xo , a.oo +b.xo ,a.oo +b.oo , a.ox+b.oo});
			ox = max({ox , a.ox +b.xx , a.oo +b.xx, a.oo+b.ox, a.ox +b.ox});
			xo = max({xo , a.xx+b.xo , a.xx+b.oo , a.xo +b.xo , a.xo +b.oo});
			xx = max({xx , a.xx+b.xx , a.xx+b.ox , a.xo+b.xx , a.xo+b.ox} );
		}
	}
	int mx(){
		return max({oo , ox , xo , xx});
	}
};
ha seg[800005];
int gg = -1e18;
void build(int id , int l , int r){
	if(l==r){
		seg[id] = {abs(p[l]), 0, 0 ,0};
		return ;
	}
	int mid = (l+r)/2;
	build(id*2 , l , mid);
	build(id*2+1 , mid+1 , r);
	seg[id].mix(seg[id*2], seg[id*2+1], mid, l , r);
}
void up(int id , int l , int r , int u){
	if(l>u||r < u) return ;
	if(l==r){
		seg[id].oo = abs(p[l]);
		return ;
	}
	int mid = (l+r)>>1;
	up(id*2 , l , mid , u );
	up(id*2+1 , mid+1 , r , u );
	seg[id].mix(seg[id*2], seg[id*2+1], mid, l , r);
}
signed main(){
//	freopen("optmilk.in","r" , stdin );
//	freopen("optmilk.out","w" , stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n , q , l , r , x; 
	cin >> n >> q ; 
	for(int i = 1 ;i <= n ; i++){
		cin >> a[i];
		if(i > 1){
			p[i-1] =a[i]-a[i-1]; 
		}
	}
	n--;
	build(1 , 1 , n );
//	cout << seg[2].ox<<" "<<seg[3].xx<<'\n';
	while(q	--){
		cin >> l >> r >> x;
		p[l-1]+=x;
		p[r]-=x;
		up(1 , 1 , n , l-1 );
		up(1 , 1 , n , r );
		cout <<seg[1].mx() <<'\n';
	}

}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 4 ms 4696 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 5 ms 4952 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 5 ms 4700 KB Output is correct
8 Correct 3 ms 4700 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 4 ms 4696 KB Output is correct
11 Correct 3 ms 4700 KB Output is correct
12 Correct 5 ms 4952 KB Output is correct
13 Correct 300 ms 26448 KB Output is correct
14 Correct 303 ms 26452 KB Output is correct
15 Correct 291 ms 26428 KB Output is correct
16 Correct 306 ms 26508 KB Output is correct
17 Correct 316 ms 26704 KB Output is correct
18 Correct 197 ms 26964 KB Output is correct