Submission #1142760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142760		Kaztaev_Alisher	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	185 ms	22876 KiB

Main

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
#define int ll

using namespace std;
using ll = long long;


const ll N = 2e5+5  , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1234567890;


int n , q , a[N] , b[N] , t[N*4][2][2];
void build(int v, int tl , int tr){
	t[v][0][0] = t[v][1][0] = t[v][0][1] = t[v][1][1] = 0; 
	if(tl == tr){
		t[v][1][1] = abs(b[tl]);
		t[v][0][1] = t[v][1][0] = t[v][0][0] = 0;
		return;
	}
	int tm = (tl+tr) >> 1;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	if(max(b[tm],b[tm+1]) > 0 && min(b[tm],b[tm+1]) < 0){
		t[v][1][1] = max(t[v*2][1][0]+t[v*2+1][1][1] , t[v*2][1][1]+t[v*2+1][0][1]);
		t[v][0][1] = max(t[v*2][0][0]+t[v*2+1][1][1] , t[v*2][0][1]+t[v*2+1][0][1]);
		t[v][1][0] = max(t[v*2][1][0]+t[v*2+1][1][0] , t[v*2][1][1]+t[v*2+1][0][0]);
		t[v][0][0] = max(t[v*2][0][0]+t[v*2+1][1][0] , t[v*2][0][1]+t[v*2+1][0][0]);
	} else {
		t[v][1][1] = t[v*2][1][1] + t[v*2+1][1][1];  
		t[v][0][1] = t[v*2][0][1] + t[v*2+1][1][1];  
		t[v][1][0] = t[v*2][1][1] + t[v*2+1][1][0];  
		t[v][0][0] = t[v*2][0][1] + t[v*2+1][1][0];
	}
}
void upd(int v, int tl , int tr , int pos , int val){
	if(tl == tr){
		b[tl] += val; 
		t[v][1][1] = abs(b[tl]);
		t[v][0][1] = t[v][1][0] = t[v][0][0] = 0;
		return;
	}
	int tm = (tl+tr) >> 1;
	if(pos <= tm) upd(v*2,tl,tm,pos,val);
	else upd(v*2+1,tm+1,tr,pos,val);
	if(max(b[tm],b[tm+1]) > 0 && min(b[tm],b[tm+1]) < 0){
		t[v][1][1] = max(t[v*2][1][0]+t[v*2+1][1][1] , t[v*2][1][1]+t[v*2+1][0][1]);
		t[v][0][1] = max(t[v*2][0][0]+t[v*2+1][1][1] , t[v*2][0][1]+t[v*2+1][0][1]);
		t[v][1][0] = max(t[v*2][1][0]+t[v*2+1][1][0] , t[v*2][1][1]+t[v*2+1][0][0]);
		t[v][0][0] = max(t[v*2][0][0]+t[v*2+1][1][0] , t[v*2][0][1]+t[v*2+1][0][0]);
	} else {
		t[v][1][1] = t[v*2][1][1] + t[v*2+1][1][1];  
		t[v][0][1] = t[v*2][0][1] + t[v*2+1][1][1];  
		t[v][1][0] = t[v*2][1][1] + t[v*2+1][1][0];  
		t[v][0][0] = t[v*2][0][1] + t[v*2+1][1][0];
	}
}
void solve(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++) {
		b[i] = a[i+1]-a[i];
		// cout << b[i] <<" ";
	}
	build(1,1,n-1);
	while(q--){
		int l , r , x;
		cin >> l >> r >> x;
		if(l-1 >= 1) upd(1,1,n-1,l-1,x);
		if(r <= n-1) upd(1,1,n-1,r,-x);
		cout << t[1][1][1] << "\n";
	}
}
/*

*/
signed main(){
	ios;
	solve();
}	

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