Cod sursa(job #1533770)

Utilizator akaprosAna Kapros akapros Data 22 noiembrie 2015 22:13:13
Problema Hotel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
#define maxN 100002
using namespace std;
int n, p;
struct aint
{
    int left;
    int right;
    int ner;
} arb[4 * maxN];
int Max(int x, int y)
{
    if (x > y)
        return x;
    return y;
}
void lazy_update(int node, int l, int r, int p, int q, int op)
{
    if (q < l || r < p)
        return;
    if (p <= l && q >= r)
    {
        if (op == 1)
            arb[node].left = arb[node].right = arb[node].ner = 0;
        else
            arb[node].left = arb[node].right = arb[node].ner = r - l + 1;
        return ;
    }
    int mid = (l + r) >> 1, lson = 2 * node, rson = 2 * node + 1;
    if (arb[node].ner == 0)
    {
        arb[lson].left = arb[lson].right = arb[lson].ner = 0;
        arb[rson].left = arb[rson].right = arb[rson].ner = 0;
    }  else
    if (arb[node].ner == r - l + 1)
    {
        arb[lson].left = arb[lson].right = arb[lson].ner = mid - l + 1;
        arb[rson].left = arb[rson].right = arb[rson].ner = r - mid;
    }
    lazy_update(lson, l, mid, p, q, op);
    lazy_update(rson, mid + 1, r, p, q, op);
    arb[node].left = arb[lson].left + ((arb[lson].left == mid - l + 1) ? arb[rson].left : 0);
    arb[node].right = arb[rson].right + ((arb[rson].right == r - mid) ? arb[lson].right : 0);
    arb[node].ner = Max(arb[lson].ner, arb[rson].ner);
    arb[node].ner = Max(arb[node].ner, arb[lson].right + arb[rson].left);
}
void read()
{
    freopen("hotel.in", "r", stdin);
    scanf("%d %d", &n, &p);
    lazy_update(1, 1, n, 1, n, 2);
}
void write()
{
    int op, x, y;
    freopen("hotel.out", "w", stdout);
    while (p --)
    {
        scanf("%d", &op);
        if (op == 3)
            printf("%d\n", arb[1].ner);
        else
        {
            scanf("%d %d", &x, &y);
            lazy_update(1, 1, n, x, x + y - 1, op);
        }
    }
}
int main()
{
    read();
    write();
    return 0;
}