Cod sursa(job #3299934)

Utilizator vladm98Munteanu Vlad vladm98 Data 11 iunie 2025 21:16:09
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <iostream>
using namespace std;

int arbIntLeft[400005];
int arbIntRight[400005];
int arbIntInterval[400005];
int lazy[400005]; // -1 - nimic, 0 - vin oameni, 1 - pleaca oameni

// update ul e cu +=
void pushLazy(int node, int left, int right) {
	if (lazy[node] == -1) return;
	if (lazy[node] == 1) {
		arbIntLeft[node] = arbIntRight[node] = arbIntInterval[node] = (right - left + 1);
	} else {
		arbIntLeft[node] = arbIntRight[node] = arbIntInterval[node] = 0;
	}
	if (left < right) {
		lazy[node << 1] = lazy[node];
		lazy[node << 1 | 1] = lazy[node];
	}
	lazy[node] = -1;
}

void updateInterval(int node, int left, int right, int a, int b, int val) {
	pushLazy(node, left, right);

	if (a <= left && right <= b) {
		lazy[node] = val;
		return;
	}

	int middle = (left + right) / 2;

	if (a <= middle) {
		updateInterval(node << 1, left, middle, a, b, val);
	}
	if (middle + 1 <= b) {
		updateInterval(node << 1 | 1, middle + 1, right, a, b, val);
	}

	pushLazy(node << 1, left, middle);
	pushLazy(node << 1 | 1, middle + 1, right);

	arbIntInterval[node] = max(arbIntRight[node << 1] + arbIntLeft[node << 1 | 1], max(arbIntInterval[node << 1], arbIntInterval[node << 1 | 1]));

	arbIntLeft[node] = arbIntLeft[node << 1] == middle - left + 1 ? arbIntLeft[node << 1] + arbIntLeft[node << 1 | 1] : arbIntLeft[node << 1];
	arbIntRight[node] = arbIntRight[node << 1 | 1] == right - middle ? arbIntRight[node << 1 | 1] + arbIntRight[node << 1] : arbIntRight[node << 1 | 1];
}


int main()
{
	freopen("hotel.in", "r", stdin);
	freopen("hotel.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= 4 * n; i++) {
		lazy[i] = -1;
	}
	updateInterval(1, 1, n, 1, n, 1);

	for (int i = 0; i < m; i++) {
		int type;
		cin >> type;
		if (type == 1) {
			int left, size;
			cin >> left >> size;
			updateInterval(1, 1, n, left, left + size - 1, 0);
		} else if (type == 2) {
			int left, size;
			cin >> left >> size;
			updateInterval(1, 1, n, left, left + size - 1, 1);
		} else {
			pushLazy(1, 1, n);
			cout << arbIntInterval[1] << '\n';
		}
	}
	return 0;
}