Submission #494329

#	Time	Username	Problem	Language	Result	Execution time	Memory
494329		8e7	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	439 ms	29556 KiB

Main

//Challenge: Accepted
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <chrono>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define ld long double
#define maxn 200005
#define mod 998244353
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll a[maxn], d[maxn];
struct segtree{
	ll seg[4 * maxn][4];
	void pull(int cur, int l, int r) {
		int m = (l + r) / 2;
		bool con = (d[m-1] >= 0) ^ (d[m] >= 0);
		for (int i = 0;i < 4;i++) seg[cur][i] = 0;
		for (int i = 0;i < 4;i++) {
			for (int j = 0;j < 4;j++) {
				if (con && (i & 2) && (j&1)) continue;
				seg[cur][(i&1) + (j&2)] = max(seg[cur][(i&1)+(j&2)], seg[cur*2][i] + seg[cur*2+1][j]);
			}
		}	
	}
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur][0] = 0;
			seg[cur][3] = abs(d[l]);
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur * 2 + 1, m, r);
		pull(cur, l, r);
	}
	void modify(int cur, int l, int r, int ind) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur][0] = 0, seg[cur][3] = abs(d[l]);
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) modify(cur*2, l, m, ind);
		else modify(cur*2+1, m, r, ind);
		pull(cur, l, r);
	}
	ll getval() {
		return *max_element(seg[1], seg[1] + 4);	
	}
} seg;
int main() {
	io
	int n, q;
	cin >> n >> q;
	for (int i = 0;i < n;i++) cin >> a[i];	
	for (int i = 0;i < n - 1;i++) d[i] = a[i+1] - a[i];	
	seg.init(1, 0, n - 1);
	while (q--) {
		int l, r, x;
		cin >> l >> r >> x;
		l--, r--;
		d[l-1] += x;d[r] -= x;
		seg.modify(1, 0, n - 1, l - 1);
		seg.modify(1, 0, n - 1, r);
		cout << seg.getval() << "\n";
	}
}
/*

4 3
1 2 3 4
1 2 1
1 1 2
2 3 1
*/

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