Submission #537827

#	Time	Username	Problem	Language	Result	Execution time	Memory
537827		Cantfindme	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	340 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 = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

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

struct dat {
	int v, vs, ve;
	int ss, se;
	dat () {}
	dat (int nv) {
		v = vs = ve = abs(nv);
		ss = se = (nv < 0);
	}

	void merge(const dat &a, const dat &b) {
		v = a.v + b.v;
		if (a.se != b.ss) v -= min(a.ve, b.vs);
		
		vs = a.vs;
		ve = b.ve;
		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: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55