# Cod sursa(job #2550024)

Utilizator Data 18 februarie 2020 11:35:53 Hotel 0 cpp-64 done Arhiva de probleme 2.63 kb
``````#include <bits/stdc++.h>

using namespace std;

const int Nmax = (1<<18) + 5;

int n, q;

class SegTree
{
int inside[Nmax], lazy[Nmax], pref[Nmax], suff[Nmax], sz[Nmax];

inline void calc(int i)
{
for(i>>=1; i; i>>=1)
if(lazy[i] == -1)
{
pref[i] = (pref[i<<1] == sz[i<<1] ? pref[i<<1] + pref[i<<1|1] : pref[i<<1]);
suff[i] = (suff[i<<1|1] == sz[i<<1|1] ? suff[i<<1|1] + suff[i<<1] : suff[i<<1|1]);
inside[i] = max( suff[i<<1] + pref[i<<1|1], max(inside[i<<1], inside[i<<1|1]) );
}
}

inline void add_lazy(int i, int tip)
{
assert(tip == 0 || tip == 1);
if(tip)
{
lazy[i] = 1;
inside[i] = suff[i] = pref[i] = sz[i];
}
else
{
lazy[i] = 0;
inside[i] = suff[i] = pref[i] = 0;
}
}

inline void propag(int i)
{
for(int h = 18; h; --h)
{
int j = i >> h;
if(j && lazy[j] != -1)
{
lazy[j] = -1;
}
}
}

public:
void init()
{
int i;
for(i=1; i<(1<<18); ++i)
lazy[i] = -1, inside[i] = pref[i] = suff[i] = 0;

for(i=(1<<17); i<(1<<18); ++i) sz[i] = 1;
for(i=(1<<17)-1; i; --i)
sz[i] = sz[i<<1] + sz[i<<1|1];

int n0 = n;
n = (1<<17);
update(0, n0, 1);
}

void update(int l, int r, int tip)
{
l += n; r += n;
int l0 = l, r0 = r;

propag(l0); propag(r0-1);

for(; l<r; l>>=1, r>>=1)
{
if(l&1)
{
assert(lazy[l] == -1 || l >= n);
++l;
}
if(r&1)
{
--r;
assert(lazy[r] == -1 || r >= n);
}
}

calc(l0); calc(r0-1);
}

int query()
{
return inside[1];
}

} aint;

int main()
{
freopen("hotel.in", "r", stdin);
freopen("hotel.out", "w", stdout);
cin.sync_with_stdio(false); cin.tie(0);

cin >> n >> q;

aint.init();

while(q--)
{
int tip, x, y;
cin >> tip;

if(tip == 1)
{
cin >> x >> y;
y += x;
aint.update(x-1, y-1, 0);
}
else if(tip == 2)
{
cin >> x >> y;
y += x;
aint.update(x-1, y-1, 1);
}
else cout << aint.query() << '\n';
}

return 0;
}
``````