Submission #1096775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096775		kamrad	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	26 ms	37980 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define IOS      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F        first
#define S        second
#define sz(x)    x.size()
#define all(x)   x.begin(), x.end()
#define pb       push_back

const int Inf    = 2e9 + 10;
const int Mod    = 1e9 + 7;
const int LG     = 25;
const int SQ     = 400;
const int Alpha  = 27;
const int maxN   = 2e5 + 10;

ll n, q;

ll a[maxN];

struct SegTree {
	struct Node {
		ll ans;
		ll L1;
		ll L2;
		ll R1;
		ll R2;
		ll lazy;
		Node() {
			ans = L1 = L2 = R1 = R2 = lazy = 0;
		}
	} t[maxN<<2];

	Node merge(Node lc, Node rc, ll L, ll R) {
		Node ret;

		if(L+2 == R) {
			ret.ans = abs(lc.R1 - rc.L1);
			ret.L1 = lc.L1;
			ret.L2 = rc.L1;
			ret.R1 = rc.R1;
			ret.R2 = lc.R1;
			return ret;
		}

		if(L+3 == R) {
			ret.L1 = lc.L1;
			ret.L2 = rc.L1;
			ret.R1 = rc.R1;
			ret.R2 = rc.R2;

			ll x = lc.R1;
			ll y = rc.L1;
			ll z = rc.L2;

			if(x <= y and y <= z) {
				ret.ans = z-x;
			}
			else if(x <= y and y >= z) {
				ret.ans = max(y-x, y-z);
			}
			else if(x >= y and y <= z) {
				ret.ans = max(x-y, z-y);
			}
			else if(x >= y and y >= z) {
				ret.ans = x-z;
			}

			return ret;
		}
		
		ret.L1 = lc.L1;
		ret.L2 = lc.L2;
		ret.R1 = rc.R1;
		ret.R2 = rc.R2;

		ll mid = (L+R)>>1;
		ll x = lc.R2;
		ll y = lc.R1;
		ll z = rc.L1;
		ll w = rc.L2;

		if(x <= y and y <= z and z <= w) {
			ret.ans = lc.ans + rc.ans + (z-y);
		}
		else if(x <= y and y <= z and z >= w) {
			ret.ans = lc.ans + rc.ans;
			if(z-y > z-w) {
				ret.ans += (z-y) - (z-w);
			}
		}
		else if(x <= y and y >= z and z <= w) {
			ret.ans = lc.ans + rc.ans;
			ret.ans += max(0LL, (y-z)-(y-x)-(w-z));
		}
		else if(x <= y and y >= z and z >= w) {
			ret.ans = lc.ans + rc.ans;
			if(y-z > y-x) {
				ret.ans += (y-z) - (y-x);
			}
		}
		else if(x >= y and y <= z and z <= w) {
			ret.ans = lc.ans + rc.ans;
			ret.ans += max(0LL, (z-y) - (x-y) - (z-w));
		}
		else if(x >= y and y <= z and z >= w) {
			ret.ans = lc.ans + rc.ans;
			ret.ans += max(0LL, (z-y) - (x-y));
		}
		else if(x >= y and y >= z and z <= w) {
			ret.ans = lc.ans + rc.ans;
			ret.ans += max(0LL, (y-z) - (x-y) - (w-z));
		}
		else if(x >= y and y >= z and z >= w) {
			ret.ans = lc.ans + rc.ans + y-z;
		}

		return ret;
	}

	void spread(ll id, ll L, ll R) {
		ll mid = (L+R)>>1;

		t[2*id+0].lazy += t[id].lazy;
		t[2*id+0].L1 += t[id].lazy;
		t[2*id+0].R1 += t[id].lazy;
		if(mid-L > 1) {
			t[2*id+0].L2 += t[id].lazy;
			t[2*id+0].R2 += t[id].lazy;
		}
		
		t[2*id+1].lazy += t[id].lazy;
		t[2*id+1].L1 += t[id].lazy;
		t[2*id+1].R1 += t[id].lazy;
		if(R-mid > 1) {
			t[2*id+1].L2 += t[id].lazy;
			t[2*id+1].R2 += t[id].lazy;
		}

		t[id].lazy = 0;
	}

	void initialize(ll id, ll L, ll R) {
		if(L+1 == R) {
			t[id].ans = 0;
			t[id].L1 = a[L];
			t[id].R1 = a[L];
			return;
		}

		ll mid = (L+R)>>1;
		initialize(2*id+0, L, mid);
		initialize(2*id+1, mid, R);

		t[id] = merge(t[2*id+0], t[2*id+1], L, R);
	}

	void update(ll id, ll L, ll R, ll l, ll r, ll x) {
		spread(id, L, R);
		
		if(L == l and R == r) {
			t[id].lazy += x;
			t[id].L1 += x;
			t[id].R1 += x;
			if(R-L > 1) {
				t[id].L2 += x;
				t[id].R2 += x;
			}

			return;
		}

		ll mid = (L+R)>>1;
		if(l < mid)
			update(2*id+0, L, mid, l, min(mid, r), x);
		if(r > mid)
			update(2*id+1, mid, R, max(l, mid), r, x);

		t[id] = merge(t[2*id+0], t[2*id+1], L, R);
	}

	Node Get(ll id, ll L, ll R, ll l, ll r) {
		spread(id, L, R);

		if(L == l and R == r)
			return t[id];

		ll mid = (L+R)>>1;
		Node lc, rc;

		if(l < mid and r <= mid) {
			return Get(2*id+0, L, mid, l, r);
		}
		if(l < mid and r > mid) {
			lc = Get(2*id+0, L, mid, l, mid);
			rc = Get(2*id+1, mid, R, mid, r);
			return merge(lc, rc, l, r);
		}
		if(l >= mid and r > mid) {
			return Get(2*id+1, mid, R, l, r);
		}

		return lc;
	}
};

int main() {
	IOS;
	
	cin >> n >> q;
	for(ll i = 1; i <= n; i++) {
		cin >> a[i];
	}

	SegTree s;
	s.initialize(1, 1, n+1);

	while(q--) {
		ll l, r, v;
		cin >> l >> r >> v;

		s.update(1, 1, n+1, l, r+1, v);
		SegTree::Node g = s.Get(1, 1, n+1, 1, n+1);
		cout << g.ans << "\n";
	}
}

Compilation message (stderr)

Main.cpp: In member function 'SegTree::Node SegTree::merge(SegTree::Node, SegTree::Node, ll, ll)':
Main.cpp:83:6: warning: unused variable 'mid' [-Wunused-variable]
   83 |   ll mid = (L+R)>>1;
      |      ^~~

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