Submission #537836

#	Time	Username	Problem	Language	Result	Execution time	Memory
537836		Cantfindme	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	638 ms	57028 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 200010;
const int INF = LLONG_MAX/4;
const int mod = 1e9+7;

int n, Q;
int A[maxn];
int diff[maxn];

struct dat {
	int v;
	int dp[2][2];
	int ss, se;
	dat () {}
	dat (int nv) {
		v = abs(nv);
		dp[1][1] = abs(nv);
		dp[0][0] = 0;
		dp[0][1] = -INF;
		dp[1][0] = -INF;
		ss = se = (nv < 0);
	}

	void merge(const dat &a, const dat &b) {
		v = 0;
		for (int i =0;i<2;i++) {
			for (int j = 0; j<2;j++) {
				dp[i][j] = max({a.dp[i][0] + b.dp[0][j], a.dp[i][0] + b.dp[1][j], a.dp[i][1] + b.dp[0][j]});
				if (a.se == b.ss) {
					dp[i][j] = max(dp[i][j], a.dp[i][1] + b.dp[1][j]);
				}
				v = max(v, dp[i][j]);
			}
		}
	
		ss = a.ss;
		se = b.se;
	}
};

struct node {
	int s, m, e;
	dat d;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
			d.merge(l -> d, r -> d);
			// cout << s << " " << e << " " << d.v << "\n";
		} else {
			diff[s] = A[s] - A[s-1];
			d = dat(A[s] - A[s-1]);
		}
	}

	void upd(int x, int nv) {
		if (s == e) {
			d = dat(nv);
		} else {
			if (x > m) r -> upd(x,nv);
			else if (x <= m) l -> upd(x,nv);
			d.merge(l -> d, r -> d);
			// cout << "UPD: " << s << " " << e << " " << d.v << "\n";
		}
	}

	int rmq() {
		return d.v;
	}
} *root;

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n >> Q;
	for (int i =1;i<=n;i++) cin >> A[i];
	A[0] = A[1];

	root = new node(1,n);
	// cout << root -> rmq() << "\n";

	for (int q = 0; q<Q;q++) {
		int l, r, x; cin >> l >> r >> x;
		
		if (l != 1) {
			diff[l] += x;
			root -> upd(l, diff[l]);
		}

		if (r+1 <= n) {
			diff[r + 1] -= x;
			root -> upd(r+1, diff[r+1]);
		}	

		// for (int i =1;i<=n;i++) cout << diff[i] << " ";
		// cout << "\n";
		cout << root -> rmq() << "\n";
	}

}

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