Cod sursa(job #3148911)

Utilizator hungntnktpHungntnktp hungntnktp Data 5 septembrie 2023 04:05:51
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
// comeback baby!

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;

struct SegmentTree {
	int L[4 * N], R[4 * N], T[4 * N], lazy[4 * N];

	tuple<int, int, int> merge(int x, int y, int l, int r) {
		int mid = (l + r) >> 1;
		int rL = (T[x] != mid - l + 1) ? L[x] : mid - l + 1 + L[y];
		int rR = (T[y] != r - mid) ? R[y] : r - mid + R[x];
		int rT = max({T[x], T[y], R[x] + L[y]});
		return make_tuple(rL, rR, rT);
	}

	void push(int s, int l, int r) {
		if (lazy[s] == 0) {
			L[s] = R[s] = T[s] = r - l + 1;
			if (l != r) lazy[s << 1] = lazy[s << 1 | 1] = 0;
			lazy[s] = -1;
		}
		if (lazy[s] == 1) {
			L[s] = R[s] = T[s] = 0;
			if (l != r) lazy[s << 1] = lazy[s << 1 | 1] = 1;
			lazy[s] = -1;
		}
	}

	void up(int s, int l, int r, int u, int v, int val) {
		push(s, l, r);
		if (l > v || r < u) return;
		if (l >= u && r <= v) {
			if (val == 0) {
				L[s] = R[s] = T[s] = r - l + 1;
				if (l != r) lazy[s << 1] = lazy[s << 1 | 1] = 0;
			}
			if (val == 1) {
				L[s] = R[s] = T[s] = 0;
				if (l != r) lazy[s << 1] = lazy[s << 1 | 1] = 1;
			}
			return;
		}
		int mid = (l + r) >> 1;
		up(s << 1, l, mid, u, v, val); up(s << 1 | 1, mid + 1, r, u, v, val);
		tie(L[s], R[s], T[s]) = merge(s << 1, s << 1 | 1, l, r);
	}
} it;

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("hotel.in", "r")) {
		freopen("hotel.in", "r", stdin);
		freopen("hotel.out", "w", stdout);
	}

	#ifdef LOCAL_MACHINE 
		if (fopen("task.in", "r")) {
			freopen("task.in", "r", stdin);
			freopen("task.ans", "w", stdout);
		}
	#endif
	
	int n, q; cin >> n >> q;
	memset(it.lazy, -1, sizeof(it.lazy));
	it.up(1, 1, n, 1, n, 0);

	while (q--) {
		int type; cin >> type;
		if (type != 3) {
			int l, x; cin >> l >> x;
			it.up(1, 1, n, l, l + x - 1, 2 - type);
		}
		else cout << it.T[1] << "\n";
	}
}

// ඞඞඞඞඞ you sus