Cod sursa(job #1869390)

Utilizator conttestecontteste12345 contteste Data 5 februarie 2017 19:40:50
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <iostream>
#include <fstream>
#define N 100000
using namespace std;
ifstream in("hotel.in");
ofstream out("hotel.out");
int n, p;
struct Node{int mxl, mxr, mxc;}sgt[N*3+5];

void update(int l, int r, int ul, int ur, int node, int o){
    if(ul<=l&&r<=ur){
        if(o==1)sgt[node].mxc=sgt[node].mxl=sgt[node].mxr=0;
        else sgt[node].mxc=sgt[node].mxl=sgt[node].mxr=r-l+1;
        return;
    }
    int m=(l+r)/2;
    if(sgt[node].mxc==r-l+1){
        sgt[node*2].mxc=sgt[node*2].mxl=sgt[node*2].mxr=m-l+1;
        sgt[node*2+1].mxc=sgt[node*2+1].mxl=sgt[node*2+1].mxr=r-m;
    }
    if(!sgt[node].mxc){
        sgt[node*2].mxc=sgt[node*2].mxl=sgt[node*2].mxr=0;
        sgt[node*2+1].mxc=sgt[node*2+1].mxl=sgt[node*2+1].mxr=0;
    }
    if(ul<=m)update(l, m, ul, ur, node*2, o);
    if(ur>m)update(m+1, r, ul, ur, node*2+1, o);
    if(sgt[node*2].mxl==m-l+1)sgt[node].mxl=sgt[node*2].mxl+sgt[node*2+1].mxl;
    else sgt[node].mxl=sgt[node*2].mxl;
    if(sgt[node*2+1].mxr==r-m)sgt[node].mxr=sgt[node*2].mxr+sgt[node*2+1].mxr;
    else sgt[node].mxr=sgt[node*2+1].mxr;
    sgt[node].mxc=max(max(sgt[node*2].mxc, sgt[node*2+1].mxc),sgt[node*2].mxr+sgt[node*2+1].mxl);
}

int main(){
    in>>n>>p;
    int x, y, z;
    sgt[1].mxc=sgt[1].mxl=sgt[1].mxr=n;
    for(int i=1; i<=p; i++){
        in>>x;
        if(x==3){
            out<<sgt[1].mxc<<"\n";
        }else{
            in>>y>>z;
            update(1, n, y, y+z-1, 1, x);
        }
    }
    return 0;
}