Cod sursa(job #3157845)

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