Cod sursa(job #1772487)

Utilizator lflorin29Florin Laiu lflorin29 Data 6 octombrie 2016 19:32:03
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

int n , p , lazy[1 << 19];

struct aint_nod {
	int best , cstart , cfn , lg;
	const aint_nod operator+ (const aint_nod &that) const {
		aint_nod need;
		need.best = max({best , that.best , cfn + that.cstart});
		need.cstart = cstart;
		if(cstart == lg) need.cstart += that.cstart;
		need.cfn = that.cfn;
		if(that.cfn == that.lg) need.cfn += cfn;
		need.lg = lg + that.lg;
		return need;
	}
}aint[1 << 19];

void init (int i , int j , int nod)
{
	aint[nod] = {j - i + 1 , j - i + 1 , j - i + 1 , j - i + 1};
	if (i == j) return;
	int m = (i + j) >> 1;
	init (i, m, nod << 1), init(m + 1, j, nod << 1 | 1);
}
void push (int nod , int i , int j)
{
	if(lazy[nod])
	{
		int use = (j - i + 1) * (lazy[nod] - 1);
		aint[nod] = {use, use, use, j - i + 1};
		lazy[nod << 1] = lazy[nod << 1 | 1] = lazy[nod], lazy[nod] = 0;
	}
}

void update (int x , int y , int i , int j , int nod , int tip)
{
	push (nod, i, j);
	if(x > j || i > y)
	{
		return;
	}
	if(i >= x && j <= y)
	{
		lazy[nod] = tip, push (nod, i, j);
		return;
	}
	int mij = (i + j) >> 1;
	update (x, y, i, mij, nod << 1, tip);
	update (x, y, mij + 1, j, nod << 1 | 1, tip);
	aint[nod] = aint[nod << 1] + aint[nod << 1 | 1];
}

int main() {
	freopen ("hotel.in", "r", stdin);
	freopen ("hotel.out", "w", stdout);

	scanf("%d %d", &n, &p);
	init(1, n, 1);

	for(; p > 0 ; --p)
	{
		int tip , i , lg , j;
		scanf("%d", &tip);
		if(tip == 3)
		{
			printf("%d\n", aint[1].best);
		}
		else
		{
			scanf("%d %d", &i , &lg);
			j = i+lg-1;
			update (i, j, 1, n, 1, tip);
		}
	}
}