Cod sursa(job #2662073)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 23 octombrie 2020 14:27:15
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <fstream>
#include <algorithm>
 
using namespace std;
 
ifstream fin("hotel.in");
ofstream fout("hotel.out");

struct node
{
    int lst, l, ldr;
};

const int N = 100005;

int n, q;
node arb[N * 4];
int lazy[N * 4];
// lazy == 0  => actualizat;
//      == 1 avem o operatie de tip 1 de aplicat;  
//      == 2 avem o operatie de tip 2 de aplicat

void updateNode(int idx, int tl, int tr)
{
    arb[idx].l = max(max(arb[idx * 2].l, arb[idx * 2 + 1].l), arb[idx * 2].ldr + arb[idx * 2 + 1].lst);

    int mid = (tl + tr) / 2;
    arb[idx].lst = arb[idx * 2].lst;
    if(arb[idx].lst == mid - tl + 1)
        arb[idx].lst += arb[idx * 2 + 1].lst;
    
    arb[idx].ldr = arb[idx * 2 + 1].ldr;
    if(arb[idx].ldr == tr - mid)
        arb[idx].ldr += arb[idx * 2].ldr;
}

void buildArb(int idx, int tl, int tr)
{
    if(tl == tr)
    {
        arb[idx] = {1, 1, 1};
        return;
    }

    int mid = (tl + tr) / 2;
    buildArb(idx * 2, tl, mid);
    buildArb(idx * 2 + 1, mid + 1, tr);

    updateNode(idx, tl, tr);
}

void updateUtil(int idx, int tl, int tr, int ql, int qr, int qt)
{
    // neactualizat?
    int lint = tr - tl + 1;
    if(lazy[idx])
    {
        if(lazy[idx] == 1)
            arb[idx] = {0, 0, 0};
        if(lazy[idx] == 2)
            arb[idx] = {lint, lint, lint};

        if(tl < tr)
            lazy[idx * 2] = lazy[idx * 2 + 1] = lazy[idx];
        
        lazy[idx] = 0;
    }

    // nu avem intersectie
    if(tr < ql || qr < tl)
        return;

    // avem intersectie totala
    if(ql <= tl && tr <= qr)
    {
        if(qt == 1)
            arb[idx] = {0, 0, 0};
        else
            arb[idx] = {lint, lint, lint};
        
        if(tl < tr)
            lazy[idx * 2] = lazy[idx * 2 + 1] = qt;
        
        return;
    }

    // intersectie partiala
    int mid = (tl + tr) / 2;
    updateUtil(idx * 2, tl, mid, ql, qr, qt);
    updateUtil(idx * 2 + 1, mid + 1, tr, ql, qr, qt);
    updateNode(idx, tl, tr);
}

void update(int ql, int qr, int qt)
{
    updateUtil(1, 1, n, ql, qr, qt);
}

int query()
{
    return arb[1].l;
}

int main()
{
    fin >> n >> q;
    buildArb(1, 1, n);
    while(q--)
    {
        int type; fin >> type;

        if(type <= 2)
        {
            int l, r, x;
            fin >> l >> x;
            r = l + x - 1;
            update(l, r, type);
        }
        else 
        {
            fout << query() << '\n';
        }
    }

    return 0;
}