Pagini recente » Cod sursa (job #2648707) | Cod sursa (job #127045) | Cod sursa (job #870739) | Cod sursa (job #836691) | Cod sursa (job #3157845)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("hotel.in");
ofstream out("hotel.out");
#define nmax 100000
int msb(int n){
int MSB=1;
while(n){
n>>=1;
MSB<<=1;
}
return MSB;
}
struct interval{
int st,dr;
bool intersects(interval i){
if(i.st>dr || st>i.dr){
return false;
}
return true;
}
bool includes(interval i){
if(st<=i.st && i.dr<=dr){
return true;
}
return false;
}
int len(){
return this->dr-this->st+1;
}
interval(){}
interval(int st,int dr){
this->st=st;
this->dr=dr;
}
};
struct Node{
int st;
int dr;
int mij;
};
Node combine(Node x,Node y){
Node comb;
comb.mij=max(max(y.mij,x.mij),x.dr+y.st);
if(x.st==x.mij && x.mij!=0){
comb.st=comb.mij;
}else{
comb.st=x.st;
}
if(y.dr==y.mij && y.mij!=0){
comb.dr=comb.mij;
}else{
comb.dr=y.dr;
}
return comb;
}
int n,narb;
int lazy[4*nmax];
Node arbint[4*nmax];
interval arb[4*nmax];
void build(){
narb=msb(n);
for(int i=narb;i<2*narb;i++){
if(i-narb+1<=n)arbint[i].st=arbint[i].dr=arbint[i].mij=1;
arb[i].st=arb[i].dr=i-narb+1;
}
for(int i=narb-1;i>0;i--){
arbint[i]=combine(arbint[2*i],arbint[2*i+1]);
arb[i].st=arb[2*i].st;
arb[i].dr=arb[2*i+1].dr;
}
}
void updateRange(int nod,interval q,int val){
if(lazy[nod]!=0){
lazy[2*nod]+=lazy[nod];
lazy[2*nod+1]+=lazy[nod];
lazy[nod]=0;
}
if(q.intersects(arb[2*nod])){
if(q.includes(arb[2*nod])){
lazy[2*nod]+=val;
}else{
updateRange(2*nod,q,val);
}
}
if(q.intersects(arb[2*nod+1])){
if(q.includes(arb[2*nod+1])){
lazy[2*nod+1]+=val;
}else{
updateRange(2*nod+1,q,val);
}
}
Node x=arbint[2*nod],y=arbint[2*nod+1];
if(lazy[2*nod]!=0){
x.st=x.dr=x.mij=0;
}
if(lazy[2*nod+1]!=0){
y.st=y.dr=y.mij=0;
}
arbint[nod]=combine(x,y);
}
int main()
{
int p;
in>>n>>p;
build();
int c,start,size;
for(int i=0;i<p;i++){
in>>c;
if(c==3){
out<<arbint[1].mij<<'\n';
}else if(c==1){
in>>start>>size;
updateRange(1,interval(start,start+size-1),1);
}
else{
in>>start>>size;
updateRange(1,interval(start,start+size-1),-1);
}
}
}