Cod sursa(job #3160410)

Utilizator mihaiBoantaMihai Boanta mihaiBoanta Data 23 octombrie 2023 22:11:00
Problema Hotel Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#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);
        }
    }    
}