Pagini recente » Cod sursa (job #1146310) | Cod sursa (job #2597006) | Cod sursa (job #2848754) | Cod sursa (job #1805208) | Cod sursa (job #3187007)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
int n, m, x, y, t;
struct ArbInt {
struct El {
int lmax = 1;
int lst = 1, lsf = 1;
int lung = 1;
int upd = 0;
};
vector<El> v;
ArbInt(int n) : v(n * 4) {
}
void init(int st = 1, int dr = n, int idx = 1) {
if (st == dr) {
return;
}
int mij = (st + dr) / 2;
// fout << st << " " << dr << " " << mij << endl;
init(st, mij, idx * 2);
init(mij + 1, dr, idx * 2 + 1);
v[idx].lung = v[idx * 2].lung + v[idx * 2 + 1].lung;
v[idx].lmax = v[idx].lung;
v[idx].lst = v[idx].lung;
v[idx].lsf = v[idx].lung;
}
void add(bool scot, int i, int j, int st = 1, int dr = n, int idx = 1) {
if (i <= st && dr <= j) {
v[idx].lmax = v[idx].lung * scot;
v[idx].lst = v[idx].lung * scot;
v[idx].lsf = v[idx].lung * scot;
}
if (st != dr) {
int mij = (st + dr) / 2;
if (i <= mij) {
add(scot, i, j, st, mij, idx * 2);
}
if (j > mij) {
add(scot, i, j, mij + 1, dr, idx * 2 + 1);
}
v[idx].lst = v[idx * 2].lst;
if (v[idx * 2].lst == v[idx * 2].lung) {
v[idx].lst += v[idx * 2 + 1].lst;
}
v[idx].lsf = v[idx * 2 + 1].lsf;
if (v[idx * 2 + 1].lsf == v[idx * 2 + 1].lung) {
v[idx].lsf += v[idx * 2].lsf;
}
v[idx].lmax =
max(max(v[idx * 2].lmax, v[idx * 2 + 1].lmax), v[idx * 2].lsf + v[idx * 2 + 1].lst);
}
}
};
int main() {
fin >> n >> m;
ArbInt a(n);
a.init();
for (int i = 0; i < m; i++) {
fin >> t;
if (t == 3) {
fout << a.v[1].lmax << endl;
} else {
fin >> x >> y;
a.add(t - 1, x, x + y - 1);
}
}
}