Submission #1146312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146312		aarb_.tomatexd	Wall (IOI14_wall)	C++20	32 / 100	3094 ms	10100 KiB

wall

#include <bits/stdc++.h>
using namespace std;

// Estructura para representar un intervalo [l, r] con un valor "val".
struct Interval {
    int l, r, val;
    Interval(int _l, int _r, int _val) : l(_l), r(_r), val(_val) {}
};

// Comparador para ordenar intervalos por su límite izquierdo.
struct IntervalCompare {
    bool operator()(const Interval &a, const Interval &b) const {
        return a.l < b.l;
    }
};

/*
Función buildWall:
    n         : número de columnas (índices 0 .. n-1).
    k         : número de fases.
    op[]      : para cada fase, 1 indica fase de "adding" y 2 fase de "removing".
    leftArr[] : columna inicial (inclusive) de la fase.
    rightArr[]: columna final (inclusive) de la fase.
    heightArr[]: el parámetro de altura de la fase.
    finalHeight[]: salida; al terminar se debe tener finalHeight[i] = número final de ladrillos en la columna i.
*/
void buildWall(int n, int k, int op[], int leftArr[], int rightArr[],
               int heightArr[], int finalHeight[]) {
    // Mantenemos la pared como un conjunto de intervalos ordenados por su inicio.
    set<Interval, IntervalCompare> intervals;
    intervals.insert(Interval(0, n - 1, 0)); // inicialmente todas las columnas tienen 0 ladrillos.

    // Función lambda "split": dado un índice pos (0 <= pos <= n), 
    // se asegura que exista un intervalo que comience exactamente en pos.
    auto split = [&](int pos) -> set<Interval, IntervalCompare>::iterator {
        if (pos > n - 1) return intervals.end();
        // Busca el primer intervalo cuyo inicio sea >= pos.
        auto it = intervals.lower_bound(Interval(pos, 0, 0));
        if (it != intervals.end() && it->l == pos)
            return it;
        // Si el intervalo que contiene pos empieza antes, retrocedemos.
        it--;
        int L = it->l, R = it->r, v = it->val;
        if (pos > R) return intervals.end(); // no debería ocurrir
        intervals.erase(it);
        // Dividimos el intervalo en [L, pos-1] y [pos, R].
        intervals.insert(Interval(L, pos - 1, v));
        return intervals.insert(Interval(pos, R, v)).first;
    };

    // Función lambda para fusionar (merge) intervalos adyacentes que tengan el mismo valor.
    // Se “recorre” desde un índice dado hasta el final de la pared.
    auto mergeFrom = [&]() {
        if (intervals.empty()) return;
        auto it = intervals.begin();
        while (it != intervals.end()) {
            auto next = it; next++;
            if (next == intervals.end()) break;
            // Si son adyacentes y tienen el mismo valor, se fusionan.
            if (it->r + 1 == next->l && it->val == next->val) {
                int L = it->l, R = next->r, v = it->val;
                // Borramos ambos intervalos y reinsertamos el fusionado.
                intervals.erase(it);
                intervals.erase(next);
                auto inserted = intervals.insert(Interval(L, R, v)).first;
                // Retrocedemos, por si se puede fusionar con el intervalo anterior.
                it = inserted;
                if (it != intervals.begin()) {
                    auto prev = it; prev--;
                    if (prev->r + 1 == it->l && prev->val == it->val) {
                        // Se fusiona con el anterior.
                        L = prev->l; R = it->r; v = it->val;
                        intervals.erase(prev);
                        intervals.erase(it);
                        it = intervals.insert(Interval(L, R, v)).first;
                    }
                }
                continue; // volvemos a probar con "it" en su nueva forma.
            } else {
                it++;
            }
        }
    };

    // Procesamos cada fase.
    for (int i = 0; i < k; i++) {
        int phaseType = op[i];       // 1: add, 2: remove.
        int L = leftArr[i];
        int R = rightArr[i];
        int h = heightArr[i];

        // Dividimos en los puntos L y R+1 para aislar la región [L, R].
        auto itR = split(R + 1);
        auto itL = split(L);

        // Recorremos todos los intervalos que caen en [L, R] y actualizamos su valor si corresponde.
        vector<Interval> updated;  // para almacenar (l, r, nuevo_valor)
        auto it = itL;
        while (it != itR) {
            int curVal = it->val;
            int newVal = curVal;
            if (phaseType == 1) {       // add: si curVal < h, se sube a h.
                if (curVal < h)
                    newVal = h;
            } else {                    // remove: si curVal > h, se baja a h.
                if (curVal > h)
                    newVal = h;
            }
            updated.push_back(Interval(it->l, it->r, newVal));
            it++;
        }
        // Borramos los intervalos que se van a actualizar.
        it = itL;
        while (it != itR) {
            auto tmp = it;
            it++;
            intervals.erase(tmp);
        }
        // Insertamos los intervalos actualizados.
        for (auto &in : updated)
            intervals.insert(in);

        // Luego, se puede haber generado “huecos” de intervalos adyacentes con el mismo valor.
        // Realizamos una fusión global.
        mergeFrom();
    }

    // Finalmente, rellenamos finalHeight[] usando los intervalos resultantes.
    for (auto it = intervals.begin(); it != intervals.end(); it++) {
        for (int j = it->l; j <= it->r; j++)
            finalHeight[j] = it->val;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39