Pagini recente » Cod sursa (job #2978657) | Cod sursa (job #363767) | Cod sursa (job #1668983) | Cod sursa (job #217935) | Cod sursa (job #3160410)
#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 max;
};
Node combine(Node x,Node y,int st,int dr){
int mij=(st+dr)/2;
Node comb;
if(x.st==mij-st+1){
comb.st=x.st+y.st;
}else{
comb.st=x.st;
}
if(y.dr==dr-mij){
comb.dr=x.dr+y.dr;
}else{
comb.dr=y.dr;
}
comb.max=max(max(x.max,y.max),x.dr+y.st);
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].max=arbint[i].st=arbint[i].dr=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[2*i].st,arb[2*i+1].dr);
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=Node();
}
if(lazy[2*nod+1]!=0){
y=Node();
}
arbint[nod]=combine(x,y,arb[nod].st,arb[nod].dr);
}
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].max<<'\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);
}
}
}