Cod sursa(job #2247238)

Utilizator ancabdBadiu Anca ancabd Data 28 septembrie 2018 09:33:09
Problema Hotel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>

using namespace std;

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

#define MAX 200001

//0 - camera ocupata
//1 - camera libera

int N, Q;
int T[MAX * 4], lst[MAX * 4], ldr[MAX * 4];

void Update(int, int, int, int, int, int);
void Fix(int, int, int);
void ConstructGraph(int, int, int);

int main()
{
    fin >> N >> Q;

    ConstructGraph(1, 1, N);

    for (int i = 1, cer, pos, l; i <= Q; i ++)
    {
        fin >> cer;

        if (cer == 3)fout << T[1] << '\n';
        else
        {
            fin >> pos >> l;

            if (cer == 1)Update(1, 1, N, pos, pos + l - 1, 0); // sosire
            else if (cer == 2)Update(1, 1, N, pos, pos + l - 1, 1); //plecare
        }
    }
    return 0;
}

void ConstructGraph(int node, int a, int b)
{

    T[node] = lst[node] = ldr[node] = b - a + 1;

    if (a >= b)
        return;

    int md = (a + b) / 2;

    ConstructGraph(2 * node, a, md);
    ConstructGraph(2 * node + 1, md + 1, b);
}


void Update(int node, int a, int b, int l, int r, int val)
{
    Fix(node, a, b);

    if (a > r || b < l)return;

    if (l <= a && b <= r)
    {
        T[node] = lst[node] = ldr[node] = val * (b - a + 1);
        Fix(node, a, b);
    }
    else
    {
        int mijl = (a + b) / 2;

        Update(2 * node, a, mijl, l, r, val);
        Update(2 * node + 1, mijl + 1, b, l, r, val);

        lst[node] = lst[2 * node];
        ldr[node] = ldr[2 * node + 1];

        if (lst[node] == mijl - a + 1)
            lst[node] += lst[2 * node + 1];

        if (ldr[node] == b - mijl)
            ldr[node] += ldr[2 * node];

        T[node] = max(lst[2 * node], ldr[2 * node + 1]);
        T[node] = max(T[node], ldr[2 * node] + lst[2 * node + 1]);
    }
}

void Fix(int i, int a, int b)
{
    if (T[i] == 0)
    {
        T[2 * i] = lst[2 * i] = ldr[2 * i] = 0;
        T[2 * i + 1] = lst[2 * i + 1] = ldr[2 * i + 1] = 0;
    }
    else if (T[i] == b - a + 1)
    {
        int mijl = (a + b) / 2;
        T[2 * i] = lst[2 * i] = ldr[2 * i] = mijl - a + 1;
        T[2 * i + 1] = lst[2 * i + 1] = ldr[2 * i + 1] = b - mijl;
    }
}