Submission #1139448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139448		vako_p	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	569 ms	80552 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,q,a[mxN],b[mxN],num[mxN];

struct segtree{
	vector<vector<ll>> v2,v3;
	ll sz = 1,res;
	pair<ll,ll> l,r;
	
	void init(){
		while(sz < n + 1) sz *= 2;
		v2.assign(2 * sz, vector<ll>(4));		
		v3.assign(2 * sz, vector<ll>(4));			
	}
	
	void merge(ll x, ll mid){
		// 0 -- 0 0 / 1 -- 1 0 / 2 -- 0 1 / 3 -- 1 1
		ll l = 2 * x + 1, r = 2 * x + 2;
		if((b[mid - 1] >= 0) != (b[mid] >= 0)){
			v3[x][0] = max(v3[l][0] + max(v3[r][0], v3[r][1]), v3[l][2] + v3[r][0]);
			v3[x][1] = max(v3[l][1] + max(v3[r][1], v3[r][0]), v3[l][3] + v3[r][0]);
			v3[x][2] = max(v3[r][2] + max(v3[l][0], v3[l][2]), v3[r][3] + v3[l][0]);
			v3[x][3] = max(v3[l][1] + max(v3[r][2], v3[r][3]), v3[l][3] + v3[r][2]);
			return;
		} 
		v3[x][0] = max(v3[l][0], v3[l][2]) + max(v3[r][0], v3[r][1]);
		v3[x][1] = max(v3[l][1], v3[l][3]) + max(v3[r][0], v3[r][1]);
		v3[x][2] = max(v3[l][0], v3[l][2]) + max(v3[r][2], v3[r][3]);
		v3[x][3] = max(v3[l][1], v3[l][3]) + max(v3[r][2], v3[r][3]);
	}
	
	void set(ll val, ll i, ll x, ll lx, ll rx){
		if(rx - lx == 1){
			v2[x][3] = abs(b[lx]);
//		cout << i << "----> " << lx << " - " << rx << "---> " << v2[x][0] << ' ' << v2[x][1] << ' ' << v2[x][2] << ' ' << v2[x][3] << '\n';
			return;
		}	
		ll mid = lx + (rx - lx) / 2;
		if(i < mid) set(val, i, 2 * x + 1, lx, mid);
		else set(val, i, 2 * x + 2, mid, rx);
		v3[2 * x + 1] = v2[2 * x + 1];
		v3[2 * x + 2] = v2[2 * x + 2];
		merge(x, mid);
		v2[x] = v3[x];
//		cout << i << "----> " << lx << " - " << rx << "---> " << v2[x][0] << ' ' << v2[x][1] << ' ' << v2[x][2] << ' ' << v2[x][3] << '\n';
	}
	
	void set(ll val, ll i){
		set(val, i, 0, 0, sz);
	}
	
	ll find(){
		return max(max(v2[0][0], v2[0][1]), max(v2[0][2],v2[0][3]));	
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("input.txt", "r", stdin);
	cin >> n >> q;
	segtree s;
	s.init();
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++) b[i] = a[i] - a[i + 1];
	for(int i = 1; i < n; i++) s.set(b[i], i);
//	cout << "---> " << s.find() << '\n';
	while(q--){
		ll l,r,x;
		cin >> l >> r >> x;
		if(r < n){
			b[r] += x;
			s.set(x, r);
		}
		if(l > 1){
			b[l - 1] -= x;
			s.set(-x, l - 1);
		} 
		cout << s.find() << '\n';
	}
} 

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