Cod sursa(job #2737281)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 4 aprilie 2021 17:01:54
Problema Hotel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("hotel.in");
ofstream g("hotel.out");

struct hotel{
	int MAX, pref, suf;
} t[400001];

bitset <400001> marked;

int N, P, op,x , y;

hotel combine(const hotel &a, const hotel &b, int tm, int tl, int tr){
	hotel res;
    res.MAX = max({a.MAX, b.MAX, a.suf + b.pref});
    res.pref = max(a.pref, a.pref + (a.pref == tm - tl + 1) * b.pref);
    res.suf = max(b.suf, b.suf + a.suf * (b.suf == tr - tm));
    return res;
}

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v].MAX = t[v].pref = t[v].suf = 1;
	}else{
		int tm = (tl + tr) >> 1;
		build(v << 1, tl, tm);
		build(v << 1 | 1, tm + 1, tr);
		t[v] = combine(t[v << 1], t[v << 1 | 1], tm, tl, tr);
	}
}

void push(int v){
	if(marked[v]){
		t[v << 1] = t[v << 1 | 1] = t[v];
		marked[v << 1] = marked[v << 1 | 1] = 1;
		marked[v] = 0;
	}
}

void update(int v, int tl, int tr, int l, int r, int new_val){
	if(l > r)
		return;
	if(l == tl && tr == r){
		t[v].MAX = t[v].pref = t[v].suf = new_val;
		marked[v] = 1;
	}else{
		push(v);
		int tm = (tl + tr) >> 1;
		update(v << 1, tl, tm, l, min(r, tm), new_val);
		update(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, new_val);
		t[v] = combine(t[v << 1], t[v << 1 | 1], tm, tl, tr);
	}
}

int main(){

	f >> N >> P;
	build(1, 1, N);

	while(P--){
		f >> op;
		if(op == 3){
			g << t[1].MAX << "\n";
		}
		if(op == 2){
			f >> x >> y;
			update(1, 1, N, x, x + y - 1, 1);
		}
		if(op == 1){
			f >> x >> y;
			update(1, 1, N, x, x + y - 1, 0);
		}
	}

}