Cod sursa(job #2104094)

Utilizator alexandru822Bosinta Alexandru alexandru822 Data 11 ianuarie 2018 09:20:53
Problema Hotel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>

using namespace std;

ifstream in("hotel.in");
ofstream out("hotel.out");

const int N_MAX = 100000;

struct Interval
{
    int sz, best, bestF, bestL;
} arbInt[4*N_MAX];

Interval join(Interval l, Interval r)
{
    Interval ans;
    ans.sz = l.sz + r.sz;
    ans.best = max(max(l.best, r.best),l.bestL+r.bestF);
    ans.bestF = l.bestF;
    if(l.best == l.sz)
        ans.bestF = l.sz + r.bestF;
    ans.bestL = r.bestL;
    if(r.best == r.sz)
        ans.bestL = r.sz + l.bestL;
    return ans;
}

void update(int node, int nodeL, int nodeR, int l, int r, bool change) // change 1 => vin, 0 => pleaca
{
    if(nodeL == nodeR)
    {
        if(change)
            arbInt[node] = {1,0,0,0};
        else
            arbInt[node] = {1,1,1,1};
        return;
    }
    int middle = (nodeL+nodeR)/2;
    if(r <= middle)
        update(2*node, nodeL, middle, l, r, change);
    else if(middle+1 <= l)
        update(2*node+1, middle+1, nodeR, l, r, change);
    else
    {
        update(2*node, nodeL, middle, l, middle, change);
        update(2*node+1, middle+1, nodeR, middle+1, r, change);
    }
    arbInt[node] = join(arbInt[2*node], arbInt[2*node+1]);
}

Interval query(int node, int nodeL, int nodeR, int l, int r)
{
    if(nodeL == l & nodeR == r)
        return arbInt[node];
    int middle = (nodeL+nodeR)/2;
    if(r <= middle)
        return query(2*node, nodeL, middle, l, r);
    if(middle+1 <= l)
        return query(2*node+1, middle+1,nodeR,l,r);
    return join(query(2*node,nodeL,middle,l,middle),query(2*node+1,middle+1,nodeR,middle+1,r));
}

int main()
{
    int n, p;
    in >> n >> p;
    for(int i = 1; i <= n; i++)
    {
        update(1,1,n,i,i,0);
    }
    for(int i = 0; i < p; i++)
    {
        int c;
        in >> c;
        if(c == 1)
        {
            int a, b;
            in >> a >> b;
            update(1,1,n,a,a+b-1,1);
        }
        else if(c == 2)
        {
            int a, b;
            in >> a >> b;
            update(1,1,n,a,a+b-1,0);
        }
        else
        {
            out << query(1,1,n,1,n).best << "\n";
        }
    }
    return 0;
}