Pagini recente » Cod sursa (job #2199792) | Cod sursa (job #2916334) | Cod sursa (job #2424036) | Cod sursa (job #1033511) | Cod sursa (job #814776)
Cod sursa(job #814776)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
const int MAX_N = 100100;
struct seg {
int left, right, current, lenght;
} segTree[MAX_N * 3];
int N, P;
void buildSegTree(int node, int lo, int hi);
void updateSegTree(int node, int lo, int hi, int a, int b, int action);
void mergeSeg(int node);
int main() {
fin >> N >> P;
buildSegTree(1, 1, N);
for (int i = 1; i <= P; ++i) {
int action;
fin >> action;
if (action == 3) {
fout << segTree[1].current << '\n';
} else {
int a, dim;
fin >> a >> dim;
updateSegTree(1, 1, N, a, a + dim - 1, action);
}
}
return 0;
}
void buildSegTree(int node, int lo, int hi) {
if (lo == hi) {
segTree[node].left = segTree[node].right = 1;
segTree[node].current = segTree[node].lenght = 1;
} else {
int mid = lo + (hi - lo) / 2;
buildSegTree(node * 2, lo, mid);
buildSegTree(node * 2 + 1, mid + 1, hi);
mergeSeg(node);
}
}
void mergeSeg(int node) {
int s1 = node * 2;
int s2 = node * 2 + 1;
segTree[node].lenght = segTree[s1].lenght + segTree[s2].lenght;
segTree[node].left = segTree[s1].left;
if (segTree[s1].left == segTree[s1].lenght) {
segTree[node].left += segTree[s2].left;
}
segTree[node].right = segTree[s2].right;
if (segTree[s2].right == segTree[s2].lenght) {
segTree[node].right += segTree[s1].right;
}
segTree[node].current = max(segTree[s1].right + segTree[s2].left,
max(segTree[s1].current, segTree[s2].current));
}
void updateSegTree(int node, int lo, int hi, int a, int b, int action) {
if (lo >= a && b >= hi) {
if (action == 1) {
segTree[node].left = segTree[node].right = segTree[node].current = 0;
} else {
segTree[node].left = segTree[node].right = segTree[node].lenght;
segTree[node].current = segTree[node].lenght;
}
} else {
int s1 = node * 2;
int s2 = node * 2 + 1;
int mid = lo + (hi - lo) / 2;
if (segTree[node].left == segTree[node].right
&& segTree[node].left == segTree[node].current) {
if (segTree[node].left == 0) {
segTree[s1].left = segTree[s1].right = segTree[s1].current = 0;
segTree[s2].left = segTree[s2].right = segTree[s2].current = 0;
} else if (segTree[node].left == segTree[node].lenght) {
segTree[s1].left = segTree[s1].right = segTree[s1].lenght;
segTree[s1].current = segTree[s1].lenght;
segTree[s2].left = segTree[s2].right = segTree[s2].lenght;
segTree[s2].current = segTree[s2].lenght;
}
}
if (a <= mid) {
updateSegTree(s1, lo, mid, a, b, action);
}
if (b > mid) {
updateSegTree(s2, mid + 1, hi, a, b, action);
}
mergeSeg(node);
}
}