Cod sursa(job #2587988)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 23 martie 2020 23:54:14
Problema Hotel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;

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

const int N = 100000;

struct interval{
    int Liber, stLiber, drLiber;
    int length;
    int lazy;
} arb[4 * N];

void unite(interval &parent, interval leftChild, interval rightChild){
    parent.Liber = max(leftChild.Liber, rightChild.Liber);
    parent.Liber = max(parent.Liber, leftChild.drLiber + rightChild.stLiber);
    parent.stLiber = leftChild.stLiber;
    parent.drLiber = rightChild.drLiber;

    if(leftChild.stLiber == leftChild.length){
        parent.Liber = max(parent.Liber, leftChild.length + rightChild.stLiber);
        parent.stLiber = leftChild.length + rightChild.stLiber;
    }
    if(rightChild.drLiber == rightChild.length){
        parent.Liber = max(parent.Liber, leftChild.drLiber + rightChild.length);
        parent.drLiber = rightChild.length + leftChild.drLiber;
    }

    parent.length = leftChild.length + rightChild.length;
}

void build(int node, int left, int right){
    if(left == right){
        arb[node].Liber = arb[node].stLiber = arb[node].drLiber = 1;
        arb[node].length = 1;
        arb[node].lazy = 0;
        return;
    }
    int middle = (left + right)/2;
    build(2*node, left, middle);
    build(2*node + 1, middle + 1, right);
    unite(arb[node], arb[2*node], arb[2*node + 1]);
}

int L, R;

void update(int node, int left, int right, int value){
    if(arb[node].lazy){
        if(left != right){
            arb[2*node].lazy += arb[node].lazy;
            arb[2*node + 1].lazy += arb[node].lazy;
        }
        arb[node].Liber += (right - left + 1) * arb[node].lazy;
        arb[node].stLiber += (right - left + 1) * arb[node].lazy;
        arb[node].drLiber += (right - left + 1) * arb[node].lazy;
        arb[node].lazy = 0;
    }
    if(left > right || right < L || left > R)
        return;
    if(L <= left && right <= R){
        arb[node].Liber += (right - left + 1) * value;
        arb[node].stLiber += (right - left + 1) * value;
        arb[node].drLiber += (right - left + 1) * value;
        if(left != right){
            arb[2*node].lazy += value;
            arb[2*node + 1].lazy += value;
        }
        return;
    }
    int middle = (left + right)/2;
    update(2*node, left, middle, value);
    update(2*node + 1, middle + 1, right, value);
    unite(arb[node], arb[2*node], arb[2*node + 1]);
}

int main()
{
    int n,p,op,i;
    fin >> n >> p;
    build(1, 1, n);
    for(i=0; i<p; i++){
        fin >> op;
        if(op == 3)
            fout << arb[1].Liber << "\n";
        else{
            fin >> L >> R;
            R = R + L - 1;
            if(op == 1)
                update(1, 1, n, -1);
            else
                update(1, 1, n, 1);
        }
    }
    return 0;
}