Submission #377666

#	Time	Username	Problem	Language	Result	Execution time	Memory
377666		maximath_1	Sjeckanje (COCI21_sjeckanje)	C++11	110 / 110	763 ms	29696 KiB

Main

#include <iostream>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <set>
#include <functional>
#include <limits.h>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 200005;
const int BLOCK = 350;
const ll mod = 998244353;

int n, q;
ll v[MX], diff[MX];
ll st[4 * MX][2][2]; // neg pos

void upd(int nd, int cl, int cr, int ps){
	if(ps < cl || cr < ps) return;
	if(cl == cr && cl == ps) return void(st[nd][1][1] = abs(diff[ps]));

	upd(nd * 2, cl, (cl + cr) / 2, ps);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, ps);

	for(int i = 0; i < 4; i ++){
		st[nd][i / 2][i % 2] = 0;
		for(int j = 0; j < 2; j ++)
			st[nd][i / 2][i % 2] = max(st[nd][i / 2][i % 2], 
				st[nd * 2][i / 2][j] + st[nd * 2 + 1][1 - j][i % 2]);
	}

	if((diff[(cl + cr) / 2] >= 0 && diff[(cl + cr) / 2 + 1] >= 0) || (diff[(cl + cr) / 2] <= 0 && diff[(cl + cr) / 2 + 1] <= 0)){
		for(int i = 0; i < 4; i ++){
			st[nd][i / 2][i % 2] = max(st[nd * 2][i / 2][0], st[nd * 2][i / 2][1]) 
					+ max(st[nd * 2 + 1][0][i % 2], st[nd * 2 + 1][1][i % 2]);
		}
	}
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> q;
	for(int i = 1; i <= n; i ++)
		cin >> v[i];
	for(int i = 1; i < n; i ++){
		diff[i] = v[i + 1] - v[i];
		upd(1, 1, n - 1, i);
	}

	for(int l, r, x; q --;){
		cin >> l >> r >> x;

		diff[r] -= x;
		upd(1, 1, n - 1, r);

		if(l - 1 > 0){
			diff[l - 1] += x;
			upd(1, 1, n - 1, l - 1);
		}

		ll ans = 0ll;
		for(int i = 0; i < 4; i ++)
			ans = max(ans, st[1][i / 2][i % 2]);
		cout << ans << endl;
	}

	return 0;
}

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