Cod sursa(job #2766605)

Utilizator DragosC1Dragos DragosC1 Data 2 august 2021 14:53:53
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <fstream>
#include <iostream>
using namespace std;

struct query {
	int tip, x, y;
};

query Q[200001];
int n, m;

void read() {
	int i;
	ifstream f("hotel.in");
	f >> n >> m;
	for (i = 1; i <= m; i++) {
		f >> Q[i].tip;
		if (Q[i].tip == 1 || Q[i].tip == 2) {
			f >> Q[i].x >> Q[i].y;
			Q[i].y = Q[i].x + Q[i].y - 1;
		}
	}
	f.close();
}

struct segment_tree {
	int lmax, lmaxst, lmaxdr;
};

segment_tree seg[600001];

segment_tree form(segment_tree a, segment_tree b, int st, int mij, int dr) {
	segment_tree aux;
	aux.lmax = max(a.lmaxdr + b.lmaxst, max(a.lmax, b.lmax));
	if (a.lmaxst == mij - st + 1)
		aux.lmaxst = a.lmaxst + b.lmaxst;
	else aux.lmaxst = a.lmaxst;
	if (b.lmaxdr == dr - (mij + 1) + 1)
		aux.lmaxdr = b.lmaxdr + a.lmaxdr;
	else aux.lmaxdr = b.lmaxdr;
	return aux;
}

void buildTree(int ind, int st, int dr) {
	if (st == dr) {
		seg[ind] = {1, 1, 1};
		return;
	}

	int mij = (st + dr) / 2;

	buildTree(ind * 2, st, mij);
	buildTree(ind * 2 + 1, mij + 1, dr);
	seg[ind] = form(seg[ind * 2], seg[ind * 2 + 1], st, mij, dr);
}

void update1(int ind, int st, int dr, int Qst, int Qdr) {
	if (st > Qdr || dr < Qst)
		return;

	int mij = (st + dr) / 2;
	if (seg[ind].lmax == dr - st + 1) {
		seg[ind * 2].lmax = seg[ind * 2].lmaxst = seg[ind * 2].lmaxdr = mij - st + 1;
		seg[ind * 2 + 1].lmax = seg[ind * 2 + 1].lmaxst = seg[ind * 2 + 1].lmaxdr = dr - mij;
	}

	if (st >= Qst && dr <= Qdr) {
		seg[ind] = {0, 0, 0};
		return;
	}
	
	update1(ind * 2, st, mij, Qst, Qdr);
	update1(ind * 2 + 1, mij + 1, dr, Qst, Qdr);

	seg[ind] = form(seg[ind * 2], seg[ind * 2 + 1], st, mij, dr);
}

void update2(int ind, int st, int dr, int Qst, int Qdr) {
	if (st > Qdr || dr < Qst)
		return;
	
	int mij = (st + dr) / 2;
	if (seg[ind].lmax == 0) {
		seg[ind * 2].lmax = seg[ind * 2].lmaxst = seg[ind * 2].lmaxdr = 0;
		seg[ind * 2 + 1].lmax = seg[ind * 2 + 1].lmaxst = seg[ind * 2 + 1].lmaxdr = 0;
	}

	if (st >= Qst && dr <= Qdr) {
		seg[ind] = {dr - st + 1, dr - st + 1, dr - st + 1};
		return;
	}

	update2(ind * 2, st, mij, Qst, Qdr);
	update2(ind * 2 + 1, mij + 1, dr, Qst, Qdr);

	seg[ind] = form(seg[ind * 2], seg[ind * 2 + 1], st, mij, dr);
}

void solve() {
	int i;
	buildTree(1, 1, n);
	ofstream g("hotel.out");
	for (i = 1; i <= m; i++) {
		if (Q[i].tip == 3) g << seg[1].lmax << '\n';
		else if (Q[i].tip == 1) update1(1, 1, n, Q[i].x, Q[i].y);
		else update2(1, 1, n, Q[i].x, Q[i].y);
	}
	g.close();
}


int main() {
	read();
	solve();
	return 0;
}