Pagini recente » Cod sursa (job #2672265) | Cod sursa (job #2958627) | Cod sursa (job #2774602) | Cod sursa (job #2724172) | Cod sursa (job #2664587)
#include <fstream>
using namespace std;
ifstream cin ("hotel.in");
ofstream cout ("hotel.out");
struct ura{
int sol, pre, suf;
};
ura seg[400005];
void julie(int nod, int st, int dr)
{
if (st == dr)
seg[nod].sol = seg[nod].pre = seg[nod].suf = 1;
else
{
int mid = (st + dr) / 2;
julie(2 * nod, st, mid);
julie(2 * nod + 1, mid + 1, dr);
seg[nod].sol = seg[nod].pre = seg[nod].suf = seg[2 * nod].sol + seg[2 * nod + 1].sol;
}
}
void update(int nod, int st, int dr, int l, int r, int tip)
{
if (l <= st && dr <= r)
seg[nod].sol = seg[nod].pre = seg[nod].suf = (dr - st + 1) * tip;
else
{
int mid = (st + dr) / 2;
if (seg[nod].sol == (1 - tip) * (dr - st + 1))
{
seg[2 * nod].sol = seg[2 * nod].pre = seg[2 * nod].suf = (mid - st + 1) * (1 - tip);
seg[2 * nod + 1].sol = seg[2 * nod + 1].pre = seg[2 * nod + 1].suf = (dr - mid) * (1 - tip);
}
if (l <= mid)
update(2 * nod, st, mid, l, r, tip);
if (r > mid)
update(2 * nod + 1, mid + 1, dr, l, r, tip);
if (seg[2 * nod].sol == mid - st + 1)
seg[nod].pre = seg[2 * nod].sol + seg[2 * nod + 1].pre;
else
seg[nod].pre = seg[2 * nod].pre;
if (seg[2 * nod + 1].sol == dr - mid)
seg[nod].suf = seg[2 * nod + 1].sol + seg[2 * nod].suf;
else
seg[nod].suf = seg[2 * nod + 1].suf;
seg[nod].sol = max(seg[nod * 2].sol, seg[nod * 2 + 1].sol);
seg[nod].sol = max(seg[nod].sol, seg[nod * 2].suf + seg[nod * 2 + 1].pre);
}
}
int main()
{
int n, k, i;
cin >> n >> k;
julie(1, 1, n);
for (i = 1; i <= k; i++)
{
int cer, a, b;
cin >> cer;
if (cer == 3)
cout << seg[1].sol << '\n';
else
{
cin >> a >> b;
update(1, 1, n, a, a + b - 1, cer - 1);
}
}
return 0;
}