Pagini recente » Cod sursa (job #2382512) | Cod sursa (job #1099972) | Cod sursa (job #2838153) | Cod sursa (job #2981275) | Cod sursa (job #2587988)
#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;
ifstream fin("hotel.in");
ofstream fout("hotel.out");
const int N = 100000;
struct interval{
int Liber, stLiber, drLiber;
int length;
int lazy;
} arb[4 * N];
void unite(interval &parent, interval leftChild, interval rightChild){
parent.Liber = max(leftChild.Liber, rightChild.Liber);
parent.Liber = max(parent.Liber, leftChild.drLiber + rightChild.stLiber);
parent.stLiber = leftChild.stLiber;
parent.drLiber = rightChild.drLiber;
if(leftChild.stLiber == leftChild.length){
parent.Liber = max(parent.Liber, leftChild.length + rightChild.stLiber);
parent.stLiber = leftChild.length + rightChild.stLiber;
}
if(rightChild.drLiber == rightChild.length){
parent.Liber = max(parent.Liber, leftChild.drLiber + rightChild.length);
parent.drLiber = rightChild.length + leftChild.drLiber;
}
parent.length = leftChild.length + rightChild.length;
}
void build(int node, int left, int right){
if(left == right){
arb[node].Liber = arb[node].stLiber = arb[node].drLiber = 1;
arb[node].length = 1;
arb[node].lazy = 0;
return;
}
int middle = (left + right)/2;
build(2*node, left, middle);
build(2*node + 1, middle + 1, right);
unite(arb[node], arb[2*node], arb[2*node + 1]);
}
int L, R;
void update(int node, int left, int right, int value){
if(arb[node].lazy){
if(left != right){
arb[2*node].lazy += arb[node].lazy;
arb[2*node + 1].lazy += arb[node].lazy;
}
arb[node].Liber += (right - left + 1) * arb[node].lazy;
arb[node].stLiber += (right - left + 1) * arb[node].lazy;
arb[node].drLiber += (right - left + 1) * arb[node].lazy;
arb[node].lazy = 0;
}
if(left > right || right < L || left > R)
return;
if(L <= left && right <= R){
arb[node].Liber += (right - left + 1) * value;
arb[node].stLiber += (right - left + 1) * value;
arb[node].drLiber += (right - left + 1) * value;
if(left != right){
arb[2*node].lazy += value;
arb[2*node + 1].lazy += value;
}
return;
}
int middle = (left + right)/2;
update(2*node, left, middle, value);
update(2*node + 1, middle + 1, right, value);
unite(arb[node], arb[2*node], arb[2*node + 1]);
}
int main()
{
int n,p,op,i;
fin >> n >> p;
build(1, 1, n);
for(i=0; i<p; i++){
fin >> op;
if(op == 3)
fout << arb[1].Liber << "\n";
else{
fin >> L >> R;
R = R + L - 1;
if(op == 1)
update(1, 1, n, -1);
else
update(1, 1, n, 1);
}
}
return 0;
}