Cod sursa(job #2227148)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 31 iulie 2018 13:25:58
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

ifstream fin ("hotel.in");
ofstream fout ("hotel.out");

const int Dim = 100001;

int  AintM[Dim * 4], AintL[Dim * 4], AintR[Dim * 4],n,m,Lazy[Dim * 4];

void Propag(int nod, int st, int dr);
void Update_Lazy(int nod, int st, int dr, int x, int y, int val);
void Build (int nod, int st, int dr);

int main() {
	
	fin >> n >> m;
	Build(1,1,n);
	int type;
	int x,y;
	for ( ; m > 0; --m) {
		fin >> type;
		if ( type == 3) {
			Propag(1,1,n);
			fout << AintM[1] << "\n";
			continue;
		}
		fin >> x >> y;
		y += x-1;
		Update_Lazy(1,1,n,x,y,type);
		
	}
}

void Update_Lazy(int nod, int st, int dr, int x, int y, int val) {
	
	if ( st >= x and dr <= y) {
		Lazy[nod] = val;
		Propag(nod,st, dr);
		return;
	}
	Propag(nod, st, dr);
	int mj = (st + dr) / 2;
	if ( mj >= x)
		Update_Lazy(nod * 2, st, mj, x , y, val);
	else
		Propag(nod * 2, st, mj);
	if ( mj < y)
		Update_Lazy(2*nod + 1, mj + 1, dr, x, y, val);
	else
		Propag(nod * 2 + 1, mj + 1, dr);
	AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2+1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
	AintL[nod] = AintL[nod * 2];
	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];
}

void Propag(int nod, int st, int dr) {
	
	if ( Lazy[nod] ) {
		if ( Lazy[nod] == 2)
			AintL[nod] = AintR[nod] = AintM[nod] = dr - st + 1;
		else
			AintL[nod] = AintR[nod] = AintM[nod] = 0;
		if ( st != dr) {
			 Lazy[2 * nod] = Lazy[2 * nod + 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);
}