Pagini recente » Cod sursa (job #2493732) | Cod sursa (job #683772) | Cod sursa (job #1966531) | Cod sursa (job #2255666) | Cod sursa (job #2851585)
#include <fstream>
// #include <iostream>
#include <vector>
using namespace std;
ifstream cin ("hotel.in");
ofstream cout ("hotel.out");
struct seg {
int left, right, max;
int add;
};
int n;
struct Aint {
int size = 1;
vector<seg> aint;
void init (int n)
{
while (size <= n)
size *= 2;
aint.resize(size * 2 + 1);
}
void build (int pos, int l, int r)
{
// cout << pos << ' ' << l << ' ' << r << '\n';
aint[pos].left = aint[pos].max = aint[pos].right = r - l + 1;
if (l < r)
{
int m = (l + r) / 2;
build (pos * 2, l, m);
build (pos * 2 + 1, m + 1, r);
}
}
void buildAint ()
{
build(1, 1, n);
}
void lazy (int pos, int s, int d, int l, int r, int val)
{
if (l > d || r < s) {
return;
}
else if (s <= l && r <= d)
{
aint[pos].add += val;
/* if (aint[pos].add == 0)
{
aint[pos].left = aint[pos].right = aint[pos].max = r - l + 1;
}
else {
aint[pos].left = aint[pos].right = aint[pos].max = 0;
}*/
}
else {
aint[pos * 2].add += aint[pos].add;
aint[pos * 2 + 1].add += aint[pos].add;
aint[pos].add = 0;
int m = (l + r) / 2;
lazy(pos * 2, s, d, l, m, val);
lazy(pos * 2 + 1, s, d, m + 1, r, val);
aint[pos].left = aint[pos * 2].left * (aint[pos * 2].add == 0);
if (aint[pos].left == m - l + 1 && aint[pos * 2 + 1].add == 0)
aint[pos].left += aint[pos * 2 + 1].left;
aint[pos].right = aint[pos * 2 + 1].right * (aint[pos * 2 + 1].add == 0);
if (aint[pos].right == r - m && aint[pos * 2].add == 0)
aint[pos].right += aint[pos * 2].right;
aint[pos].max = max (aint[pos * 2].max * (aint[pos * 2].add == 0),
aint[pos * 2 + 1].max * (aint[pos * 2 + 1].add == 0));
aint[pos].max = max (aint[pos].max, aint[pos * 2].right * (aint[pos * 2].add == 0)
+ aint[pos * 2 + 1].left * (aint[pos * 2 + 1].add == 0));
// cout << pos << ' ' << l << ' ' << r << ' ' << aint[pos].max << '\n';
}
}
void lazyUpdate (int s, int d, int val)
{
lazy(1, s, d, 1, n, val);
}
};
int main ()
{
int q, c;
int s, m;
cin >> n >> q;
struct Aint aint;
aint.init(n);
aint.buildAint();
while (q--)
{
cin >> c;
if (c == 3)
{
cout << aint.aint[1].max << '\n';
}
else if (c == 1)
{
cin >> s >> m;
aint.lazyUpdate(s, s + m - 1, 1);
}
else {
cin >> s >> m;
aint.lazyUpdate(s, s + m - 1, -1);
}
}
}