Submission #500678

#	Time	Username	Problem	Language	Result	Execution time	Memory
500678		Eyed	Sjeckanje (COCI21_sjeckanje)	C++14	0 / 110	12 ms	25292 KiB

Main

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;

//Task Sjeckanje
//COCI 2021: https://oj.uz/problem/view/COCI21_sjeckanje

ll n, q;
ll lazy[800020];
bool mark[800020];

void push(ll v) {
	if (mark[v]) {
		lazy[2 * v] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
		lazy[v] = 0;
		mark[v] = false;
		mark[2 * v] = true;
		mark[2 * v + 1] = true;
	}
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll x) {
	if (l > r) return;
	if (l <= tl && r >= tr) {
		lazy[v] += x;
		mark[v] = true;
		return;
	}
	push(v);
	ll mid = (tl + tr) / 2;
	update(2 * v, tl, mid, max(l, tl), min(r, mid), x);
	update(2 * v + 1, mid + 1, tr, max(l, mid + 1), min(r, tr), x);
} void update(ll l, ll r, ll x) { update(1, 0, n-1, l, r, x); }
ll get(ll v, ll tl, ll tr, ll x) {
	if (tl == tr) return lazy[v];
	push(v);
	ll mid = (tl + tr) / 2;
	if (x <= mid) return get(2 * v, tl, mid, x);
	else return get(2 * v + 1, mid + 1, tr, x);
} ll get(ll x) { return get(1, 0, n-1, x);}

struct node {
	ll lt; //0 if non-decreasing, 1 if decreasing
	ll rt; //0 if non-decreasing, 1 if decreasing
	ll sum;
	bool eq;
	node(ll l = 0, ll r = 0, ll s = 0, bool e = false) : lt(l), rt(r), sum(s), eq(e) {};
};

node seg[800020];
void upd(ll v, ll tl, ll tr, ll l, ll r, ll x) {
	if (l > r) return;
	if (l <= tl && r >= tr) {
		return;
	}
	ll mid = (tl + tr) / 2;
	upd(2 * v, tl, mid, max(l, tl), min(r, mid), x);
	upd(2 * v + 1, mid + 1, tr, max(mid + 1, l), min(tr, r), x);
	ll a = get(mid);
	ll b = get(mid + 1);
	if (tr - tl == 1) {
		seg[v].eq = false;
		if (b < a) {
			seg[v].lt = 1;
			seg[v].rt = 0;
		}
		if (b > a) {
			seg[v].lt = 0;
			seg[v].rt = 1;
		}
		if (a == b) {
			seg[v].eq = true;
			seg[v].lt = -1;
			seg[v].rt = -1;
		}
		seg[v].sum = abs(a - b);
		return;
	}
	seg[v].eq = seg[2 * v].eq & seg[2 * v + 1].eq;
	if (a != b && seg[v].eq) {
		seg[v].eq = false;
		if (a < b) {
			seg[v].lt = 0;
			seg[v].rt = 1;
		}
		if (a > b) {
			seg[v].lt = 1;
			seg[v].rt = 0;
		}
		seg[v].sum = abs(b - a);
		return;
	}
	seg[v].lt = seg[2 * v].lt;
	seg[v].rt = seg[2 * v + 1].rt;
	if ((seg[v].lt == -1 || seg[v].rt == -1) && !(seg[v].eq)) {
		if (seg[v].lt == -1) {
			if (a > b) seg[v].lt = 1;
			if (a < b) seg[v].lt = 0;
			if (a == b) seg[v].lt = seg[2 * v + 1].lt;
		}
		if (seg[v].rt == -1) {
			if (a > b) seg[v].rt = 0;
			if (a < b) seg[v].rt = 1;
			if (a == b) seg[v].rt = seg[2 * v].rt;
		}
	}
	seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum;

	if (seg[2 * v].rt == 0 && seg[2 * v + 1].lt == 0) {
		if (a > b && a > get(mid + 2)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + a - get(mid + 2);
		if (a < b && b > get(mid - 1)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + b - get(mid - 1);
	}
	if (seg[2 * v].rt == 1 && seg[2 * v + 1].lt == 1) {
		if (a > b && get(mid - 1) > b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid - 1) - b;
		if (a < b && get(mid + 2) > a) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid + 2) - a;
	}
	if (seg[2 * v].rt == 0 && seg[2 * v + 1].lt == 1) {
		if (a > b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + a - b;
		if (a < b && get(mid + 2) > get(mid - 1)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid + 2) - get(mid - 1);
	}
	if (seg[2 * v].rt == 1 && seg[2 * v + 1].lt == 0) {
		if (a < b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + b - a;
		if (a > b && get(mid - 1) > get(mid + 2)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid - 1) - get(mid + 2);
	}
	if (!seg[v].eq) {
		if (seg[2 * v].eq) {
			if (seg[2 * v + 1].lt == 0) {
				if (a < b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + b - a;
				if (a > b && a > get(mid + 2)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + a - get(mid + 2);
			}
			if (seg[2 * v + 1].lt == 1) {
				if (a > b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + a - b;
				if (a < b && a < get(mid + 2)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid + 2) - a;
			}
		}
		if (seg[2 * v + 1].eq) {
			if (seg[2 * v].rt == 0) {
				if (b < a) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + a - b;
				if (b > a && b > get(mid - 1)) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + b - get(mid - 1);
			}
			if (seg[2 * v].rt == 1) {
				if (b > a) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + b - a;
				if (b < a && get(mid - 1) > b) seg[v].sum = seg[2 * v].sum + seg[2 * v + 1].sum + get(mid - 1) - b;
			}
		}
	}
}
void upd(ll l, ll r, ll x) {
	update(l, r, x);
	upd(1, 0, n-1, l, r, x);
}

void build(ll v, ll tl, ll tr) {
	ll mid = (tl + tr) / 2;
	seg[v].eq = true;
	seg[v].lt = -1;
	seg[v].rt = -1;
	seg[v].sum = 0;
	if (tl != tr) {
		build(2 * v, tl, mid);
		build(2 * v + 1, mid + 1, tr);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> q;
	build(1, 0, n - 1);
	for (ll i = 0; i < n; ++i) {
		ll x;
		cin >> x;
		upd(i, i, x);
	}
	cout << seg[1].sum << endl;
	for (ll i = 0; i < q; ++i) {
		ll l, r, x;
		cin >> l >> r >> x;
		upd(l-1, r-1, x);
		cout << seg[1].sum << endl;
	}

	return 0;
}

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