Cod sursa(job #2656246)

Utilizator IRadu1529Radu Ionescu IRadu1529 Data 7 octombrie 2020 11:00:57
Problema Hotel Scor 0
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");

const int NMAX = 100005;
int n, m;

int v[NMAX + 1];
int lazy[NMAX + 1];
int frunza[NMAX + 1];
int AintL[4 * NMAX];// -subsecventa de suma maxima care incepe din st lui nod si se termina tot in intervalul lui
int AintR[4 * NMAX];// -subsecventa de suma maxima care se termina pe dr lui nod
int AintM[4 * NMAX]; //-subscventa de suma maxima din intervalul lui nod

void propagare(int nod, int l, int r) {
	if (lazy[nod]) {
		if (lazy[nod] == 1)
			AintL[nod] = AintR[nod] = AintM[nod] = r - l + 1;
		else
			AintL[nod] = AintR[nod] = AintM[nod] = -10;
		if (frunza[nod] == 0)
			lazy[nod * 2] = lazy[nod];
		if (frunza[nod] == 0)
			lazy[nod * 2 + 1] = lazy[nod];
		lazy[nod] = 0;
	}
}

void Build(int nod, int st, int dr) {
	AintL[nod] = AintR[nod] = AintM[nod] = dr - st + 1;
	if (st == dr)
		return;
	int mj = (st + dr) / 2;
	Build(2 * nod, st, mj);
	Build(2 * nod + 1, mj + 1, dr);
}

void update(int nod, int l, int r, int st, int dr, int val) {
	propagare(nod, l, r);
	if (l >= st and r <= dr) {
		lazy[nod] = val;
		propagare(nod, st, dr);
		return;
	}
	int mj = (l + r) / 2;
	if (st <= mj)
		update(nod * 2, l, mj, st, dr, val);
	if (dr > mj)
		update(nod * 2 + 1, mj + 1, r, st, dr, val);
	propagare(nod * 2, l, mj);
	propagare(nod * 2 + 1, mj + 1, r);
	AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2 + 1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
	if (AintL[nod] == mj - st + 1)
		AintL[nod] += AintL[nod * 2 + 1];
	AintR[nod] = AintR[nod * 2 + 1];
	if (AintR[nod] == dr - mj)
		AintR[nod] += AintR[nod * 2];
}

int main() {
	int x, y, type;
	fin >> n >> m;
	Build(1, 1, n);
	for (int i = 1; i <= m; ++i) {
		fin >> type;

		if (type == 3) {
			propagare(1, 1, n);
			fout << AintM[1] << "\n";
			continue;
		}
		fin >> x >> y;
		int val = 1;
		if (type == 1)
			val = -10;

		update(1, 1, n, x, x + y - 1, val);
	}
}