Кодерун съездил в отпуск и привёз множество распеч...

Question

Кодерун съездил в отпуск и привёз множество распечатанных фотографий. Чтобы сохранить воспоминания, он решил расставить их в один ряд на своей длинной-предлинной полке. Делает он это так: ищет на полке самое левое свободное место подходящего размера (фотографии бывают разной ширины), и ставит туда фотографию. Иногда фотография кажется недостаточно хорошей, и Кодерун её снимает — таким образом, на полке образуются пропуски.

Если непрерывного свободного места подходящего для очередной фотографии нет, но суммарно пустого пространства на полке хватает, Кодерун делает элегантное движение лапкой: сдвигает все стоящие фотографии влево так, чтобы они стояли вплотную друг к другу без промежутков, сохраняя свой изначальный относительный порядок. После этого в освободившееся место справа он ставит фотографию.

Но прежде, чем заняться делом, нужно всё тщательно планировать, и Кодерун обратился за помощью к ИИ.

ИИ-агент попытался написать программу, которая будет отслеживать положение каждой фотографии: написал быстрый ввод, реализовал АВЛ-дерево для поиска подходящих свободных мест на полке, и оно даже работает. Но выяснилось, что на больших тестах программа всё равно подтормаживает: поиск нужного места и симуляция сдвига фотографий иногда занимают слишком много времени.

Помогите Кодеруну доделать программу так, чтобы она успевала обрабатывать все его действия!

Полка имеет длину M M сантиметров. Изначально она абсолютно пуста (все M M сантиметров свободны).

Далее Кодерун совершает N N действий двух типов:

text
ADD s — поставить на полку фотографию шириной s s сантиметров;
DEL k — снять с полки фотографию, которая была поставлена в результате k k-го действия.

Команды нумеруются с 1 1 в порядке поступления.

Команда DEL k всегда ссылается на корректную ранее выполненную команду ADD, фотография от которой всё ещё стоит на полке.

При выполнении команды ADD s Кодерун ищет на полке самое левое непрерывное свободное место шириной не меньше s s. Если такое место найдено, он ставит туда фотографию, выравнивая её по левому краю этого свободного отрезка (занимая ровно s s сантиметров).

Если непрерывного свободного места подходящего размера нет, но суммарно пустого пространства на полке хватает, Кодерун сдвигает все стоящие фотографии влево так, чтобы они стояли вплотную друг к другу без промежутков, сохраняя свой изначальный относительный порядок. Вся свободная часть полки при этом собирается в один пустой отрезок справа. После этого логика команды ADD s выполняется снова (и в этот раз фотография успешно помещается).

Если же суммарного свободного места на полке меньше s s, поставить фотографию невозможно. В этом случае нужно вывести строку OVERFLOW, затем текущее расположение всех стоящих на полке фотографий и завершить программу.

После успешной обработки всех N N команд нужно вывести итоговое расположение всех фотографий на полке.

Для каждой фотографии нужно вывести координату её левого края и её ширину. Фотографии выводятся по порядку слева направо (в порядке возрастания координат).

Координаты на полке отсчитываются от левого края начиная с 0 0.
Формат ввода

text
В первой строке содержатся два целых числа M M и  N N — длина полки в сантиметрах и количество действий Кодеруна.
Далее следуют N N строк. Каждая строка содержит одну команду одного из двух видов:
    ADD s
    DEL k

Ограничения:

text
1 ≤ M ≤ 1 09 1≤M≤109
1 ≤ N ≤ 3 ⋅ 1 06 1≤N≤3⋅106
здесь s s — ширина фотографии, которую нужно поставить, а  k k — номер команды, в результате которой была поставлена убираемая фотография.
команды нумеруются подряд с  1 1.
гарантируется, что номер после DEL соответствует команде ADD, для которой команда DEL ещё не вызывалась.

Формат вывода

Если при обработке очередной команды ADD на полке не хватает места для фотографии даже после сдвига, выведите строку:

OVERFLOW

После этого выведите текущее расположение всех находящихся на полке фотографий и завершите программу.

Если все команды обработаны успешно, выведите итоговое расположение всех фотографий.

Каждая фотография выводится в отдельной строке в формате:

coordinate width

где coordinate — текущая координата левого края фотографии (от 0 0), а width — её ширина.

Фотографии должны быть выведены слева направо (в порядке возрастания координат).

Если полка оказалась пуста, ничего выводить не нужно.
Примечание

В качестве шаблона в редакторе кода приведено решение, которое написал ИИ-агент. Логика в нём верная, но работает оно медленно. Можно взять его за основу и доделать, а можно написать целиком с нуля.
Ограничения

Ограничение времени
2,5 с
Ограничение памяти
384 МБ

Примеры
Пример 1
Ввод

10 4
ADD 3
ADD 2
DEL 1
ADD 4

Вывод

3 2
5 4

Пример 2
Ввод

10 5
ADD 3
ADD 3
ADD 3
DEL 2
ADD 4

Вывод

0 3
3 3
6 4

Пример 3
Ввод

10 4
ADD 4
ADD 4
ADD 3
ADD 1

Вывод

OVERFLOW
0 4
4 4

// Наивное решение задачи о фотографиях на полке.
// GNU C++20, самодостаточный файл.
//
// ─── Идея ────────────────────────────────────────────────────────────────────
// Два АВЛ-дерева (ключ → значение):
// free_gaps : координата левого края свободного отрезка → его длина
// placed_photos : координата левого края фотографии → номер действия (action_id)
//
// Массивы coord_of[action_id] и width_of[action_id] — O(1)-поиск при DEL.
//
// ADD: inorder-обход free_gaps → первый свободный отрезок подходящей ширины, O(N).
// DEL: find + predecessor для слияния соседей, O(log N).
// Вывод: inorder placed_photos — уже упорядочено, std::sort не нужен.

#include <cstdint>
#include <cstdio>
#include <memory>
#include <utility>
#include <vector>

// ─── Fast I/O ─────────────────────────────────────────────────────────────────

namespace io {

text
static constexpr int BUF_SIZE = 1 << 16;   // 64 КБ
static char buf[BUF_SIZE];
static int  pos = 0, len = 0;

void init() { len = (int)fread(buf, 1, BUF_SIZE, stdin); }

inline char peek() {
    if (pos < len) return buf[pos];
    len = (int)fread(buf, 1, BUF_SIZE, stdin);
    pos = 0;
    return pos < len ? buf[pos] : '\0';
}

inline void skip_ws() { while (peek() != '\0' && peek() <= ' ') ++pos; }

inline uint64_t read_uint() {
    while (peek() != '\0' && peek() <= ' ') ++pos;
    uint64_t x = 0;
    while (peek() >= '0') { x = x * 10 + (uint64_t)(buf[pos++] - '0'); }
    return x;
}

inline char read_op() {
    while (peek() != '\0' && peek() <= ' ') ++pos;
    char first = buf[pos++];
    while (peek() != '\0' && peek() > ' ') ++pos;
    return first;
}

} // namespace io

// ─── АВЛ-дерево ───────────────────────────────────────────────────────────────
//
// Балансированное бинарное дерево поиска с инвариантом AVL:
// для каждого узла |height(left) − height(right)| ≤ 1.
//
// Это гарантирует высоту O(log N) и, следовательно, O(log N) для
// insert / erase / find / predecessor.
//
// Inorder-обход (left → node → right) посещает узлы
// в порядке возрастания ключей — без дополнительной сортировки.

template<typename Key, typename Value>
class AVLMap {
public:
struct Node {
Key key;
Value value;
int height = 1;
std::unique_ptr<Node> left, right;

text
    Node(Key k, Value v) : key(std::move(k)), value(std::move(v)) {}
};

using NodePtr = std::unique_ptr<Node>;

// ── Интерфейс ─────────────────────────────────────────────────────────

void insert(Key key, Value value) {
    root_ = insert_impl(std::move(root_), std::move(key), std::move(value));
}

void erase(const Key& key) {
    root_ = erase_impl(std::move(root_), key);
}

// Найти узел по ключу; nullptr если нет.
Node* find(const Key& key) const {
    Node* p = root_.get();
    while (p) {
        if      (key < p->key) p = p->left.get();
        else if (key > p->key) p = p->right.get();
        else                   return p;
    }
    return nullptr;
}

// Наибольший ключ строго меньше key (predecessor); nullptr если нет.
Node* predecessor(const Key& key) const {
    Node* p = root_.get(), *result = nullptr;
    while (p) {
        if (p->key < key) { result = p; p = p->right.get(); }
        else                p = p->left.get();
    }
    return result;
}

// Найти первый (по inorder) узел, для которого pred(key, value) == true.
// Используется для leftmost-fit поиска свободного отрезка.
template<typename Pred>
Node* first_where(Pred pred) const {
    return first_where_impl(root_.get(), pred);
}

// Inorder-обход; fn(const Key&, const Value&).
template<typename Fn>
void inorder(Fn fn) const { inorder_impl(root_.get(), fn); }

bool empty() const { return !root_; }

private:
NodePtr root_;

text
// ── Вспомогательные ───────────────────────────────────────────────────

static int height(const NodePtr& p)       { return p ? p->height : 0; }
static int balance_factor(const NodePtr& p) {
    return p ? height(p->right) - height(p->left) : 0;
}
static void update_height(NodePtr& p) {
    if (p) p->height = 1 + std::max(height(p->left), height(p->right));
}

// Правое вращение: исправляет левый перевес.
//        p                  q
//       / \               /   \
//      q   C    =>       A     p
//     / \                     / \
//    A   B                   B   C
static NodePtr rotate_right(NodePtr p) {
    auto q   = std::move(p->left);
    p->left  = std::move(q->right);
    update_height(p);
    q->right = std::move(p);
    update_height(q);
    return q;
}

// Левое вращение: исправляет правый перевес.
static NodePtr rotate_left(NodePtr q) {
    auto p   = std::move(q->right);
    q->right = std::move(p->left);
    update_height(q);
    p->left  = std::move(q);
    update_height(p);
    return p;
}

// Перебалансировка снизу вверх после вставки / удаления.
static NodePtr rebalance(NodePtr p) {
    update_height(p);
    int bf = balance_factor(p);

    if (bf == 2) {
        // Правое поддерево слишком высокое.
        if (balance_factor(p->right) < 0)
            p->right = rotate_right(std::move(p->right)); // RL-случай
        return rotate_left(std::move(p));
    }
    if (bf == -2) {
        // Левое поддерево слишком высокое.
        if (balance_factor(p->left) > 0)
            p->left = rotate_left(std::move(p->left));    // LR-случай
        return rotate_right(std::move(p));
    }
    return p;
}

static NodePtr insert_impl(NodePtr p, Key key, Value value) {
    if (!p) return std::make_unique<Node>(std::move(key), std::move(value));
    if      (key < p->key) p->left  = insert_impl(std::move(p->left),  std::move(key), std::move(value));
    else if (key > p->key) p->right = insert_impl(std::move(p->right), std::move(key), std::move(value));
    else                   p->value = std::move(value);
    return rebalance(std::move(p));
}

// Извлечь минимальный узел: {узел, остаток дерева}.
static std::pair<NodePtr, NodePtr> extract_min(NodePtr p) {
    if (!p->left) return {std::move(p), std::move(p->right)};
    auto [min_node, new_left] = extract_min(std::move(p->left));
    p->left = std::move(new_left);
    return {std::move(min_node), rebalance(std::move(p))};
}

static NodePtr erase_impl(NodePtr p, const Key& key) {
    if (!p) return nullptr;
    if (key < p->key) { p->left  = erase_impl(std::move(p->left),  key); return rebalance(std::move(p)); }
    if (key > p->key) { p->right = erase_impl(std::move(p->right), key); return rebalance(std::move(p)); }
    // Нашли узел.
    if (!p->left)  return std::move(p->right);
    if (!p->right) return std::move(p->left);
    // Два поддерева: заменяем inorder-преемником.
    auto [successor, new_right] = extract_min(std::move(p->right));
    successor->left  = std::move(p->left);
    successor->right = std::move(new_right);
    return rebalance(std::move(successor));
}

template<typename Pred>
static Node* first_where_impl(Node* p, Pred& pred) {
    if (!p) return nullptr;
    // Сначала ищем в левом поддереве (меньшие ключи = «левее»).
    if (Node* found = first_where_impl(p->left.get(), pred)) return found;
    // Затем проверяем текущий узел.
    if (pred(p->key, p->value)) return p;
    // Если не нашли — ищем в правом.
    return first_where_impl(p->right.get(), pred);
}

template<typename Fn>
static void inorder_impl(const Node* p, Fn& fn) {
    if (!p) return;
    inorder_impl(p->left.get(), fn);
    fn(p->key, p->value);
    inorder_impl(p->right.get(), fn);
}

};

// ─── Полка с фотографиями ──────────────────────────────────────────────────────

class Shelf {
public:
explicit Shelf(uint64_t shelf_length, uint64_t max_actions)
: total_free_length_(shelf_length)
, coord_of_(max_actions + 1, 0)
, width_of_ (max_actions + 1, 0)
{
free_gaps_.insert(0, shelf_length);
}

text
// Поставить фотографию шириной width. Возвращает false при OVERFLOW.
bool add(uint64_t width, uint64_t action_id) {
    if (width > total_free_length_) return false;

    // Leftmost fit: самый левый свободный отрезок длиной >= width.
    auto* fit = free_gaps_.first_where(
        [width](uint64_t /*coord*/, uint64_t gap_len) {
            return gap_len >= width;
        });

    if (!fit) {
        compact();
        fit = free_gaps_.first_where(
            [width](uint64_t, uint64_t gap_len) {
                return gap_len >= width;
            });
    }

    uint64_t gap_coord = fit->key;
    uint64_t gap_len   = fit->value;

    free_gaps_.erase(gap_coord);
    if (gap_len > width)
        free_gaps_.insert(gap_coord + width, gap_len - width);

    placed_photos_.insert(gap_coord, action_id);
    coord_of_[action_id] = gap_coord;
    width_of_[action_id]  = width;
    total_free_length_ -= width;
    return true;
}

void del(uint64_t action_id) {
    const uint64_t coord          = coord_of_[action_id];
    const uint64_t original_width = width_of_[action_id];

    placed_photos_.erase(coord);
    total_free_length_ += original_width;
    free_gaps_.insert(coord, original_width);

    // Слить с правым соседом (если он тоже свободен).
    uint64_t right_key = coord + original_width;
    if (auto* rn = free_gaps_.find(right_key)) {
        uint64_t merged = original_width + rn->value;
        free_gaps_.erase(right_key);
        free_gaps_.insert(coord, merged);
    }

    // Слить с левым соседом (если он тоже свободен).
    if (auto* ln = free_gaps_.predecessor(coord)) {
        if (ln->key + ln->value == coord) {
            uint64_t left_coord = ln->key;
            uint64_t left_len   = ln->value;
            uint64_t cur_len    = free_gaps_.find(coord)->value;
            free_gaps_.erase(coord);
            free_gaps_.insert(left_coord, left_len + cur_len);
        }
    }
}

// Вывод стоящих фотографий в порядке координат (inorder, без sort).
void print_placed() const {
    placed_photos_.inorder([this](uint64_t coord, uint64_t action_id) {
        printf("%llu %llu\n",
               (unsigned long long)(coord),
               (unsigned long long)width_of_[action_id]);
    });
}

private:
AVLMap<uint64_t, uint64_t> free_gaps_;
AVLMap<uint64_t, uint64_t> placed_photos_;
std::vector<uint64_t> coord_of_;
std::vector<uint64_t> width_of_;
uint64_t total_free_length_;

text
// Сдвиг влево: прижать все стоящие фотографии к левому краю полки.
void compact() {
    struct Entry { uint64_t action_id, new_coord; };
    std::vector<Entry> entries;
    uint64_t cursor = 0;

    placed_photos_.inorder([&](uint64_t /*old_coord*/, uint64_t action_id) {
        entries.push_back({action_id, cursor});
        coord_of_[action_id] = cursor;
        cursor += width_of_[action_id];
    });

    free_gaps_      = {};
    placed_photos_ = {};
    if (total_free_length_ > 0)
        free_gaps_.insert(cursor, total_free_length_);
    for (auto& e : entries)
        placed_photos_.insert(e.new_coord, e.action_id);
}

};

// ─── main ─────────────────────────────────────────────────────────────────────

int main() {
io::init();
uint64_t shelf_length = io::read_uint();
uint64_t num_actions = io::read_uint();
if (shelf_length == 0) return 0;

text
Shelf shelf(shelf_length, num_actions);
bool overflow = false;

for (uint64_t action_id = 1; action_id <= num_actions; ++action_id) {
    char op = io::read_op();
    if (op == 'A') {
        uint64_t width = io::read_uint();
        if (!overflow && !shelf.add(width, action_id)) {
            printf("OVERFLOW\n");
            overflow = true;
        }
    } else {
        uint64_t target_action = io::read_uint();
        if (!overflow) shelf.del(target_action);
    }
}

shelf.print_placed();
return 0;

}

Answer 1

Идея

Будем хранить фотографии как последовательность в splay-дереве.

Перед всеми фотографиями добавим фиктивную фотографию ширины 0. Для каждого узла храним:

ширину фотографии;
длину свободного участка сразу после неё;
максимальную длину такого участка во всём поддереве.

Например:

text
[фиктивная] gap [фото] gap [фото] gap ...

Тогда операции выглядят так:

ADD: найти самый левый узел, после которого свободно хотя бы s; вставить новую фотографию сразу после него.
DEL: удалить фотографию, а её ширину и свободный участок после неё присоединить к промежутку после предыдущей фотографии.
Сдвиг влево: лениво присвоить всем промежуткам значение 0, а после последней фотографии записать суммарную свободную длину.

Таким образом, при уплотнении фотографии физически не перемещаются и координаты не пересчитываются.

Сложность:

ADD, DEL, уплотнение — амортизированно O(log N);
итоговый вывод — O(K), где K — число оставшихся фотографий;
память — O(N).

GNU C++20

cpp
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <vector>

// -----------------------------------------------------------------------------
// Fast input
// -----------------------------------------------------------------------------

class FastInput {
    static constexpr std::size_t BUF_SIZE = 1u << 20;

    char buffer_[BUF_SIZE];
    std::size_t position_ = 0;
    std::size_t length_ = 0;

    inline char getChar() {
        if (position_ == length_) {
            length_ = std::fread(buffer_, 1, BUF_SIZE, stdin);
            position_ = 0;

            if (length_ == 0) {
                return '\0';
            }
        }

        return buffer_[position_++];
    }

public:
    uint32_t readUInt() {
        char c = getChar();

        while (c <= ' ') {
            c = getChar();
        }

        uint32_t value = 0;

        while (c >= '0' && c <= '9') {
            value = value * 10u + static_cast<uint32_t>(c - '0');
            c = getChar();
        }

        return value;
    }

    char readOperation() {
        char c = getChar();

        while (c != 'A' && c != 'D') {
            c = getChar();
        }

        const char result = c;

        // Пропускаем остаток слова ADD или DEL.
        do {
            c = getChar();
        } while (c > ' ');

        return result;
    }
};

// -----------------------------------------------------------------------------
// Fast output
// -----------------------------------------------------------------------------

class FastOutput {
    static constexpr std::size_t BUF_SIZE = 1u << 20;

    char buffer_[BUF_SIZE];
    std::size_t position_ = 0;

    inline void ensure(std::size_t required) {
        if (position_ + required > BUF_SIZE) {
            flush();
        }
    }

public:
    ~FastOutput() {
        flush();
    }

    void flush() {
        if (position_ != 0) {
            std::fwrite(buffer_, 1, position_, stdout);
            position_ = 0;
        }
    }

    void writeOverflow() {
        static constexpr char text[] = "OVERFLOW\n";

        ensure(sizeof(text) - 1);

        for (char c : text) {
            if (c == '\0') {
                break;
            }

            buffer_[position_++] = c;
        }
    }

    void writePair(uint32_t coordinate, uint32_t width) {
        ensure(32);

        char digits[16];
        int count = 0;

        do {
            digits[count++] =
                static_cast<char>('0' + coordinate % 10u);
            coordinate /= 10u;
        } while (coordinate != 0);

        while (count != 0) {
            buffer_[position_++] = digits[--count];
        }

        buffer_[position_++] = ' ';

        count = 0;

        do {
            digits[count++] =
                static_cast<char>('0' + width % 10u);
            width /= 10u;
        } while (width != 0);

        while (count != 0) {
            buffer_[position_++] = digits[--count];
        }

        buffer_[position_++] = '\n';
    }
};

// -----------------------------------------------------------------------------
// Shelf
// -----------------------------------------------------------------------------

class Shelf {
    // В старшем бите parent_and_flag хранится ленивое обнуление промежутков.
    static constexpr uint32_t LAZY_ZERO = 0x80000000u;
    static constexpr uint32_t PARENT_MASK = 0x7fffffffu;

    struct Node {
        uint32_t left = 0;
        uint32_t right = 0;

        // Младшие 31 бит — parent, старший бит — lazy zero.
        uint32_t parent_and_flag = 0;

        uint32_t width = 0;
        uint32_t gap_after = 0;
        uint32_t max_gap = 0;
    };

    std::vector<Node> tree_;
    std::vector<uint32_t> stack_;

    // Узел 0 — null.
    // Узел 1 — фиктивная фотография перед началом полки.
    uint32_t root_ = 1;

    uint32_t total_free_;

    inline uint32_t parent(uint32_t node) const {
        return tree_[node].parent_and_flag & PARENT_MASK;
    }

    inline bool hasLazyZero(uint32_t node) const {
        return (tree_[node].parent_and_flag & LAZY_ZERO) != 0;
    }

    inline void setParent(uint32_t node, uint32_t new_parent) {
        if (node == 0) {
            return;
        }

        tree_[node].parent_and_flag =
            (tree_[node].parent_and_flag & LAZY_ZERO) |
            new_parent;
    }

    // Лениво обнулить все gap_after в поддереве.
    inline void applyZero(uint32_t node) {
        if (node == 0) {
            return;
        }

        tree_[node].gap_after = 0;
        tree_[node].max_gap = 0;
        tree_[node].parent_and_flag |= LAZY_ZERO;
    }

    inline void push(uint32_t node) {
        if (!hasLazyZero(node)) {
            return;
        }

        applyZero(tree_[node].left);
        applyZero(tree_[node].right);

        tree_[node].parent_and_flag &= PARENT_MASK;
    }

    inline void pull(uint32_t node) {
        tree_[node].max_gap = std::max(
            tree_[node].gap_after,
            std::max(
                tree_[tree_[node].left].max_gap,
                tree_[tree_[node].right].max_gap
            )
        );
    }

    void rotate(uint32_t node) {
        const uint32_t p = parent(node);
        const uint32_t g = parent(p);

        const bool node_is_right = tree_[p].right == node;

        const uint32_t middle =
            node_is_right ? tree_[node].left : tree_[node].right;

        if (node_is_right) {
            tree_[p].right = middle;
            tree_[node].left = p;
        } else {
            tree_[p].left = middle;
            tree_[node].right = p;
        }

        setParent(middle, p);
        setParent(p, node);
        setParent(node, g);

        if (g == 0) {
            root_ = node;
        } else if (tree_[g].left == p) {
            tree_[g].left = node;
        } else {
            tree_[g].right = node;
        }

        pull(p);
        pull(node);
    }

    // Все ленивые операции на пути root -> node уже должны быть раскрыты.
    void splayPushed(uint32_t node) {
        while (parent(node) != 0) {
            const uint32_t p = parent(node);
            const uint32_t g = parent(p);

            if (g != 0) {
                const bool same_direction =
                    (tree_[p].left == node) ==
                    (tree_[g].left == p);

                if (same_direction) {
                    rotate(p);
                } else {
                    rotate(node);
                }
            }

            rotate(node);
        }
    }

    // Используется, когда узел найден напрямую по номеру команды.
    void pushPathAndSplay(uint32_t node) {
        uint32_t count = 0;

        for (uint32_t current = node;
             current != 0;
             current = parent(current)) {
            stack_[count++] = current;
        }

        while (count != 0) {
            push(stack_[--count]);
        }

        splayPushed(node);
    }

    // Найти самый левый промежуток длины не меньше width.
    // Гарантируется, что такой промежуток существует.
    uint32_t findLeftmostFit(uint32_t width) {
        uint32_t node = root_;

        while (true) {
            push(node);

            const uint32_t left = tree_[node].left;

            if (tree_[left].max_gap >= width) {
                node = left;
            } else if (tree_[node].gap_after >= width) {
                splayPushed(node);
                return node;
            } else {
                node = tree_[node].right;
            }
        }
    }

    // Уплотнить фотографии:
    // все внутренние промежутки становятся нулевыми,
    // весь свободный участок помещается после последней фотографии.
    void compact() {
        applyZero(root_);

        uint32_t last = root_;

        while (true) {
            push(last);

            if (tree_[last].right == 0) {
                break;
            }

            last = tree_[last].right;
        }

        splayPushed(last);

        tree_[last].gap_after = total_free_;
        pull(last);
    }

    // root_ — фотография, после которой нужно вставить новую.
    void insertAfterRoot(uint32_t node_id, uint32_t width) {
        const uint32_t old_gap = tree_[root_].gap_after;
        const uint32_t old_right = tree_[root_].right;

        tree_[node_id].left = 0;
        tree_[node_id].right = old_right;
        tree_[node_id].parent_and_flag = root_;

        tree_[node_id].width = width;
        tree_[node_id].gap_after = old_gap - width;
        tree_[node_id].max_gap = old_gap - width;

        setParent(old_right, node_id);

        tree_[root_].right = node_id;
        tree_[root_].gap_after = 0;

        pull(node_id);
        pull(root_);
    }

public:
    Shelf(uint32_t shelf_length, uint32_t action_count)
        : tree_(static_cast<std::size_t>(action_count) + 2),
          stack_(static_cast<std::size_t>(action_count) + 2),
          total_free_(shelf_length) {
        tree_[1].gap_after = shelf_length;
        tree_[1].max_gap = shelf_length;
    }

    bool add(uint32_t width, uint32_t action_id) {
        if (width > total_free_) {
            return false;
        }

        if (tree_[root_].max_gap >= width) {
            findLeftmostFit(width);
        } else {
            // Суммарного места достаточно, но подходящего цельного
            // промежутка нет.
            compact();
        }

        // Для команды action_id используется узел action_id + 1.
        insertAfterRoot(action_id + 1u, width);

        total_free_ -= width;
        return true;
    }

    void erase(uint32_t add_action_id) {
        const uint32_t victim = add_action_id + 1u;

        pushPathAndSplay(victim);

        const uint32_t left_root = tree_[victim].left;
        const uint32_t right_root = tree_[victim].right;

        // К промежутку после предыдущей фотографии добавятся:
        // ширина удаляемой фотографии и промежуток после неё.
        const uint32_t released =
            tree_[victim].width + tree_[victim].gap_after;

        total_free_ += tree_[victim].width;

        setParent(left_root, 0);
        setParent(right_root, 0);

        // Слева всегда находится хотя бы фиктивный узел.
        root_ = left_root;

        // Последний узел левой части — непосредственный предшественник victim.
        uint32_t predecessor = root_;

        while (true) {
            push(predecessor);

            if (tree_[predecessor].right == 0) {
                break;
            }

            predecessor = tree_[predecessor].right;
        }

        splayPushed(predecessor);

        tree_[root_].gap_after += released;

        tree_[root_].right = right_root;
        setParent(right_root, root_);

        pull(root_);
    }

    void print(FastOutput& out) {
        uint32_t stack_size = 0;
        uint32_t current = root_;
        uint32_t coordinate = 0;

        // Итеративный inorder-обход.
        while (current != 0 || stack_size != 0) {
            while (current != 0) {
                push(current);
                stack_[stack_size++] = current;
                current = tree_[current].left;
            }

            current = stack_[--stack_size];

            if (current != 1) {
                out.writePair(coordinate, tree_[current].width);
            }

            coordinate +=
                tree_[current].width +
                tree_[current].gap_after;

            current = tree_[current].right;
        }
    }
};

// -----------------------------------------------------------------------------
// Main
// -----------------------------------------------------------------------------

int main() {
    FastInput input;
    FastOutput output;

    const uint32_t shelf_length = input.readUInt();
    const uint32_t action_count = input.readUInt();

    Shelf shelf(shelf_length, action_count);

    for (uint32_t action_id = 1;
         action_id <= action_count;
         ++action_id) {
        const char operation = input.readOperation();
        const uint32_t argument = input.readUInt();

        if (operation == 'A') {
            if (!shelf.add(argument, action_id)) {
                output.writeOverflow();
                shelf.print(output);
                return 0;
            }
        } else {
            shelf.erase(argument);
        }
    }

    shelf.print(output);
    return 0;
}

Решение проверено на примерах и случайными тестами сравнением с прямой симуляцией.

Answer 2

Это задача на кратчайшую общую надстроку, она NP-трудна. Поэтому гарантировать прохождение порога качества для произвольных тестов невозможно, но следующий алгоритм значительно сильнее приведённого бейзлайна:

Точно удаляет строки, являющиеся подстроками других.
Рассматривает объединения строк глобально, а не только добавление к текущему ответу.
Находит все возможные перекрытия без квадратичного перебора пар.
Несколько раз запускает жадный алгоритм с разными вариантами разрешения равенств.
Для маленького числа оставшихся строк использует точное динамическое программирование.

Пусть последняя строка цепочки — a, первая строка другой цепочки — b. Если суффикс a длины l совпадает с префиксом b длины l, цепочки можно объединить, сэкономив l символов.

Для поиска таких совпадений строится суффиксный массив. Для каждой длины l объединяются соседние суффиксы с LCP >= l. В одной компоненте оказываются позиции, с которых начинаются одинаковые строки длины l.

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

struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU() = default;

    explicit DSU(int n) {
        init(n);
    }

    void init(int n) {
        parent.resize(n);
        size.assign(n, 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int v) {
        while (parent[v] != v) {
            parent[v] = parent[parent[v]];
            v = parent[v];
        }
        return v;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) {
            return false;
        }

        if (size[a] < size[b]) {
            swap(a, b);
        }

        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};

// -----------------------------------------------------------------------------
// Suffix array
// -----------------------------------------------------------------------------

static vector<int> buildSuffixArray(const vector<unsigned char>& text) {
    const int n = static_cast<int>(text.size());

    vector<int> suffixArray(n);
    vector<int> classes(n);
    vector<int> temporary(n);
    vector<int> count(max(n, 256));

    constexpr int alphabetSize = 28;

    fill(count.begin(), count.begin() + alphabetSize, 0);

    for (unsigned char c : text) {
        ++count[c];
    }

    for (int i = 1; i < alphabetSize; ++i) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; --i) {
        suffixArray[--count[text[i]]] = i;
    }

    int classCount = 0;

    for (int i = 0; i < n; ++i) {
        if (i == 0 || text[suffixArray[i]] != text[suffixArray[i - 1]]) {
            ++classCount;
        }

        classes[suffixArray[i]] = classCount - 1;
    }

    for (int shift = 1; classCount < n; shift <<= 1) {
        int position = 0;

        for (int i = max(0, n - shift); i < n; ++i) {
            temporary[position++] = i;
        }

        for (int suffix : suffixArray) {
            if (suffix >= shift) {
                temporary[position++] = suffix - shift;
            }
        }

        fill(count.begin(), count.begin() + classCount, 0);

        for (int suffix : temporary) {
            ++count[classes[suffix]];
        }

        for (int i = 1; i < classCount; ++i) {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; --i) {
            int suffix = temporary[i];
            suffixArray[--count[classes[suffix]]] = suffix;
        }

        swap(classes, temporary);

        int newClassCount = 1;
        classes[suffixArray[0]] = 0;

        for (int i = 1; i < n; ++i) {
            int previous = suffixArray[i - 1];
            int current = suffixArray[i];

            bool different =
                temporary[previous] != temporary[current];

            if (!different) {
                int previousSecond =
                    previous + shift < n
                        ? temporary[previous + shift]
                        : -1;

                int currentSecond =
                    current + shift < n
                        ? temporary[current + shift]
                        : -1;

                different = previousSecond != currentSecond;
            }

            if (different) {
                ++newClassCount;
            }

            classes[current] = newClassCount - 1;
        }

        classCount = newClassCount;
    }

    return suffixArray;
}

static vector<int> buildRank(const vector<int>& suffixArray) {
    vector<int> rank(suffixArray.size());

    for (int i = 0; i < static_cast<int>(suffixArray.size()); ++i) {
        rank[suffixArray[i]] = i;
    }

    return rank;
}

static vector<int> buildLCP(
    const vector<unsigned char>& text,
    const vector<int>& suffixArray,
    const vector<int>& rank
) {
    const int n = static_cast<int>(text.size());

    vector<int> lcp(n, 0);
    int common = 0;

    for (int position = 0; position < n; ++position) {
        int suffixRank = rank[position];

        if (suffixRank == 0) {
            continue;
        }

        int previousPosition = suffixArray[suffixRank - 1];

        while (
            position + common < n &&
            previousPosition + common < n &&
            text[position + common] ==
                text[previousPosition + common]
        ) {
            ++common;
        }

        lcp[suffixRank] = common;

        if (common > 0) {
            --common;
        }
    }

    return lcp;
}

// -----------------------------------------------------------------------------
// Exact solution for small instances
// -----------------------------------------------------------------------------

static int calculateOverlap(const string& left, const string& right) {
    int limit = static_cast<int>(
        min(left.size(), right.size())
    );

    string combined;
    combined.reserve(2 * limit + 1);

    combined.append(right.data(), limit);
    combined.push_back('{');
    combined.append(
        left.data() + left.size() - limit,
        limit
    );

    vector<int> prefix(combined.size(), 0);

    for (int i = 1; i < static_cast<int>(combined.size()); ++i) {
        int matched = prefix[i - 1];

        while (
            matched > 0 &&
            combined[i] != combined[matched]
        ) {
            matched = prefix[matched - 1];
        }

        if (combined[i] == combined[matched]) {
            ++matched;
        }

        prefix[i] = matched;
    }

    return prefix.back();
}

static string solveExactly(
    const vector<string>& strings,
    const vector<int>& active
) {
    const int n = static_cast<int>(active.size());

    vector<vector<int>> overlap(
        n,
        vector<int>(n, 0)
    );

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                overlap[i][j] = calculateOverlap(
                    strings[active[i]],
                    strings[active[j]]
                );
            }
        }
    }

    const int maskCount = 1 << n;
    constexpr int negativeInfinity = -1'000'000'000;

    vector<int> dp(
        static_cast<size_t>(maskCount) * n,
        negativeInfinity
    );

    vector<int8_t> previous(
        static_cast<size_t>(maskCount) * n,
        -1
    );

    for (int i = 0; i < n; ++i) {
        dp[static_cast<size_t>(1 << i) * n + i] = 0;
    }

    for (int mask = 1; mask < maskCount; ++mask) {
        size_t base = static_cast<size_t>(mask) * n;

        for (int last = 0; last < n; ++last) {
            int current = dp[base + last];

            if (current == negativeInfinity) {
                continue;
            }

            int remaining = (maskCount - 1) ^ mask;

            while (remaining != 0) {
                int bit = remaining & -remaining;
                int next = __builtin_ctz(
                    static_cast<unsigned>(bit)
                );

                int nextMask = mask | bit;
                int candidate =
                    current + overlap[last][next];

                size_t index =
                    static_cast<size_t>(nextMask) * n + next;

                if (candidate > dp[index]) {
                    dp[index] = candidate;
                    previous[index] =
                        static_cast<int8_t>(last);
                }

                remaining -= bit;
            }
        }
    }

    const int fullMask = maskCount - 1;
    int last = 0;

    for (int i = 1; i < n; ++i) {
        if (
            dp[static_cast<size_t>(fullMask) * n + i] >
            dp[static_cast<size_t>(fullMask) * n + last]
        ) {
            last = i;
        }
    }

    vector<int> order;
    int mask = fullMask;

    while (last != -1) {
        order.push_back(last);

        int predecessor =
            previous[static_cast<size_t>(mask) * n + last];

        mask ^= 1 << last;
        last = predecessor;
    }

    reverse(order.begin(), order.end());

    string answer = strings[active[order[0]]];

    for (int i = 1; i < n; ++i) {
        int left = order[i - 1];
        int right = order[i];

        answer.append(
            strings[active[right]],
            overlap[left][right],
            string::npos
        );
    }

    return answer;
}

// -----------------------------------------------------------------------------
// Greedy solution
// -----------------------------------------------------------------------------

struct Record {
    uint32_t key;
    uint32_t id;
};

struct Level {
    vector<Record> prefixes;
    vector<Record> suffixes;
};

struct RandomGenerator {
    uint64_t state;

    explicit RandomGenerator(uint64_t seed)
        : state(seed) {}

    uint64_t next() {
        state += 0x9e3779b97f4a7c15ULL;

        uint64_t value = state;

        value =
            (value ^ (value >> 30)) *
            0xbf58476d1ce4e5b9ULL;

        value =
            (value ^ (value >> 27)) *
            0x94d049bb133111ebULL;

        return value ^ (value >> 31);
    }

    int index(int size) {
        return static_cast<int>(
            next() % static_cast<uint64_t>(size)
        );
    }
};

static void addTopLevel(
    array<uint16_t, 4>& levels,
    uint8_t& count,
    int level
) {
    if (count < levels.size()) {
        levels[count++] = static_cast<uint16_t>(level);
    }
}

static int findFallbackLevel(
    const array<uint16_t, 4>& levels,
    uint8_t count,
    int currentLevel
) {
    for (int i = 0; i < count; ++i) {
        if (levels[i] < currentLevel) {
            return levels[i];
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> strings(n);
    vector<int> starts(n);
    vector<int> lengths(n);

    vector<unsigned char> text;
    text.reserve(2'020'000);

    for (int i = 0; i < n; ++i) {
        cin >> strings[i];

        starts[i] = static_cast<int>(text.size());
        lengths[i] = static_cast<int>(strings[i].size());

        for (char c : strings[i]) {
            text.push_back(
                static_cast<unsigned char>(c - 'a' + 2)
            );
        }

        // Символ 1 меньше всех букв и отсутствует в строках.
        text.push_back(1);
    }

    vector<int> suffixArray = buildSuffixArray(text);
    vector<int> rank = buildRank(suffixArray);
    vector<int> lcp = buildLCP(
        text,
        suffixArray,
        rank
    );

    // Строка содержится в другой строке тогда и только тогда,
    // когда один из соседей её суффикса в suffix array имеет
    // общий префикс не короче всей строки.
    vector<char> contained(n, false);

    for (int i = 0; i < n; ++i) {
        int currentRank = rank[starts[i]];

        if (
            (
                currentRank > 0 &&
                lcp[currentRank] >= lengths[i]
            ) ||
            (
                currentRank + 1 <
                    static_cast<int>(suffixArray.size()) &&
                lcp[currentRank + 1] >= lengths[i]
            )
        ) {
            contained[i] = true;
        }
    }

    vector<int> active;
    active.reserve(n);

    int maximumLength = 0;
    long long activeTotalLength = 0;

    for (int i = 0; i < n; ++i) {
        if (!contained[i]) {
            active.push_back(i);
            maximumLength = max(
                maximumLength,
                lengths[i]
            );
            activeTotalLength += lengths[i];
        }
    }

    if (active.size() == 1) {
        cout << strings[active[0]] << '\n';
        return 0;
    }

    if (active.size() <= 18) {
        cout << solveExactly(strings, active) << '\n';
        return 0;
    }

    const int activeCount =
        static_cast<int>(active.size());

    /*
     * lcp[i] — LCP суффиксов suffixArray[i - 1]
     * и suffixArray[i].
     *
     * Для заданной длины l объединяем все такие пары,
     * для которых lcp[i] >= l. После этого два суффикса
     * находятся в одной компоненте тогда и только тогда,
     * когда их первые l символов равны.
     */
    vector<vector<int>> edgesByLength(
        maximumLength + 1
    );

    for (int i = 1; i < static_cast<int>(lcp.size()); ++i) {
        int common = min(lcp[i], maximumLength);

        if (common > 0) {
            edgesByLength[common].push_back(i);
        }
    }

    vector<int> countAtLeast(
        maximumLength + 2,
        0
    );

    for (int original : active) {
        ++countAtLeast[lengths[original]];
    }

    for (int length = maximumLength - 1;
         length >= 1;
         --length) {
        countAtLeast[length] +=
            countAtLeast[length + 1];
    }

    vector<Level> levels(maximumLength + 1);

    for (int length = 1;
         length <= maximumLength;
         ++length) {
        levels[length].prefixes.reserve(
            countAtLeast[length]
        );

        levels[length].suffixes.reserve(
            countAtLeast[length]
        );
    }

    // DSU работает с позициями в suffix array, а не с
    // позициями исходного текста.
    DSU equalPrefixes(static_cast<int>(text.size()));

    for (int overlapLength = maximumLength;
         overlapLength >= 1;
         --overlapLength) {
        for (int position :
             edgesByLength[overlapLength]) {
            equalPrefixes.unite(
                position - 1,
                position
            );
        }

        auto& prefixes =
            levels[overlapLength].prefixes;

        auto& suffixes =
            levels[overlapLength].suffixes;

        for (int id = 0; id < activeCount; ++id) {
            int original = active[id];

            if (lengths[original] < overlapLength) {
                continue;
            }

            int prefixPosition = starts[original];

            int suffixPosition =
                starts[original] +
                lengths[original] -
                overlapLength;

            prefixes.push_back({
                static_cast<uint32_t>(
                    equalPrefixes.find(
                        rank[prefixPosition]
                    )
                ),
                static_cast<uint32_t>(id)
            });

            suffixes.push_back({
                static_cast<uint32_t>(
                    equalPrefixes.find(
                        rank[suffixPosition]
                    )
                ),
                static_cast<uint32_t>(id)
            });
        }

        auto compareRecords = [](
            const Record& left,
            const Record& right
        ) {
            if (left.key != right.key) {
                return left.key < right.key;
            }

            return left.id < right.id;
        };

        sort(
            prefixes.begin(),
            prefixes.end(),
            compareRecords
        );

        sort(
            suffixes.begin(),
            suffixes.end(),
            compareRecords
        );
    }

    // Большие структуры суффиксного массива больше не нужны.
    vector<unsigned char>().swap(text);
    vector<int>().swap(suffixArray);
    vector<int>().swap(rank);
    vector<int>().swap(lcp);
    vector<vector<int>>().swap(edgesByLength);

    /*
     * Для первой попытки оцениваем, насколько хороший
     * следующий вариант есть у каждой вершины.
     *
     * Если следующего хорошего варианта нет, такую вершину
     * желательно использовать раньше.
     */
    vector<array<uint16_t, 4>> topOutgoing(
        activeCount
    );

    vector<array<uint16_t, 4>> topIncoming(
        activeCount
    );

    vector<uint8_t> outgoingCount(
        activeCount,
        0
    );

    vector<uint8_t> incomingCount(
        activeCount,
        0
    );

    for (int overlapLength = maximumLength;
         overlapLength >= 1;
         --overlapLength) {
        const auto& prefixes =
            levels[overlapLength].prefixes;

        const auto& suffixes =
            levels[overlapLength].suffixes;

        size_t suffixIndex = 0;
        size_t prefixIndex = 0;

        while (
            suffixIndex < suffixes.size() &&
            prefixIndex < prefixes.size()
        ) {
            if (
                suffixes[suffixIndex].key <
                prefixes[prefixIndex].key
            ) {
                uint32_t key =
                    suffixes[suffixIndex].key;

                while (
                    suffixIndex < suffixes.size() &&
                    suffixes[suffixIndex].key == key
                ) {
                    ++suffixIndex;
                }

                continue;
            }

            if (
                prefixes[prefixIndex].key <
                suffixes[suffixIndex].key
            ) {
                uint32_t key =
                    prefixes[prefixIndex].key;

                while (
                    prefixIndex < prefixes.size() &&
                    prefixes[prefixIndex].key == key
                ) {
                    ++prefixIndex;
                }

                continue;
            }

            uint32_t key = suffixes[suffixIndex].key;

            size_t nextSuffixIndex = suffixIndex;
            size_t nextPrefixIndex = prefixIndex;

            while (
                nextSuffixIndex < suffixes.size() &&
                suffixes[nextSuffixIndex].key == key
            ) {
                ++nextSuffixIndex;
            }

            while (
                nextPrefixIndex < prefixes.size() &&
                prefixes[nextPrefixIndex].key == key
            ) {
                ++nextPrefixIndex;
            }

            for (size_t i = suffixIndex;
                 i < nextSuffixIndex;
                 ++i) {
                int source = suffixes[i].id;

                bool hasAnotherTarget =
                    nextPrefixIndex - prefixIndex >= 2 ||
                    static_cast<int>(
                        prefixes[prefixIndex].id
                    ) != source;

                if (hasAnotherTarget) {
                    addTopLevel(
                        topOutgoing[source],
                        outgoingCount[source],
                        overlapLength
                    );
                }
            }

            for (size_t i = prefixIndex;
                 i < nextPrefixIndex;
                 ++i) {
                int target = prefixes[i].id;

                bool hasAnotherSource =
                    nextSuffixIndex - suffixIndex >= 2 ||
                    static_cast<int>(
                        suffixes[suffixIndex].id
                    ) != target;

                if (hasAnotherSource) {
                    addTopLevel(
                        topIncoming[target],
                        incomingCount[target],
                        overlapLength
                    );
                }
            }

            suffixIndex = nextSuffixIndex;
            prefixIndex = nextPrefixIndex;
        }
    }

    int attemptCount;

    if (activeTotalLength <= 200'000) {
        attemptCount = 64;
    } else if (activeTotalLength <= 800'000) {
        attemptCount = 32;
    } else {
        attemptCount = 16;
    }

    vector<int> bestNext;
    vector<int> bestPrevious;
    vector<uint16_t> bestOverlapLength;

    long long bestSavedLength = -1;

    vector<int> availableSources;
    vector<int> availableTargets;

    availableSources.reserve(activeCount);
    availableTargets.reserve(activeCount);

    for (int attempt = 0;
         attempt < attemptCount;
         ++attempt) {
        vector<int> next(activeCount, -1);
        vector<int> previous(activeCount, -1);

        vector<uint16_t> overlapLengthAfter(
            activeCount,
            0
        );

        DSU chains(activeCount);

        long long savedLength = 0;

        RandomGenerator random(
            0x123456789abcdef0ULL +
            0x9e3779b97f4a7c15ULL *
                static_cast<uint64_t>(attempt + 1)
        );

        for (int overlapLength = maximumLength;
             overlapLength >= 1;
             --overlapLength) {
            const auto& prefixes =
                levels[overlapLength].prefixes;

            const auto& suffixes =
                levels[overlapLength].suffixes;

            size_t suffixIndex = 0;
            size_t prefixIndex = 0;

            while (
                suffixIndex < suffixes.size() &&
                prefixIndex < prefixes.size()
            ) {
                if (
                    suffixes[suffixIndex].key <
                    prefixes[prefixIndex].key
                ) {
                    uint32_t key =
                        suffixes[suffixIndex].key;

                    while (
                        suffixIndex < suffixes.size() &&
                        suffixes[suffixIndex].key == key
                    ) {
                        ++suffixIndex;
                    }

                    continue;
                }

                if (
                    prefixes[prefixIndex].key <
                    suffixes[suffixIndex].key
                ) {
                    uint32_t key =
                        prefixes[prefixIndex].key;

                    while (
                        prefixIndex < prefixes.size() &&
                        prefixes[prefixIndex].key == key
                    ) {
                        ++prefixIndex;
                    }

                    continue;
                }

                uint32_t key = suffixes[suffixIndex].key;

                size_t nextSuffixIndex = suffixIndex;
                size_t nextPrefixIndex = prefixIndex;

                while (
                    nextSuffixIndex < suffixes.size() &&
                    suffixes[nextSuffixIndex].key == key
                ) {
                    ++nextSuffixIndex;
                }

                while (
                    nextPrefixIndex < prefixes.size() &&
                    prefixes[nextPrefixIndex].key == key
                ) {
                    ++nextPrefixIndex;
                }

                availableSources.clear();
                availableTargets.clear();

                for (size_t i = suffixIndex;
                     i < nextSuffixIndex;
                     ++i) {
                    int source = suffixes[i].id;

                    if (next[source] == -1) {
                        availableSources.push_back(source);
                    }
                }

                for (size_t i = prefixIndex;
                     i < nextPrefixIndex;
                     ++i) {
                    int target = prefixes[i].id;

                    if (previous[target] == -1) {
                        availableTargets.push_back(target);
                    }
                }

                // Первая попытка использует эвристику regret.
                if (attempt == 0) {
                    sort(
                        availableSources.begin(),
                        availableSources.end(),
                        [&](int left, int right) {
                            int leftFallback =
                                findFallbackLevel(
                                    topOutgoing[left],
                                    outgoingCount[left],
                                    overlapLength
                                );

                            int rightFallback =
                                findFallbackLevel(
                                    topOutgoing[right],
                                    outgoingCount[right],
                                    overlapLength
                                );

                            if (
                                leftFallback !=
                                rightFallback
                            ) {
                                return
                                    leftFallback >
                                    rightFallback;
                            }

                            return left > right;
                        }
                    );

                    sort(
                        availableTargets.begin(),
                        availableTargets.end(),
                        [&](int left, int right) {
                            int leftFallback =
                                findFallbackLevel(
                                    topIncoming[left],
                                    incomingCount[left],
                                    overlapLength
                                );

                            int rightFallback =
                                findFallbackLevel(
                                    topIncoming[right],
                                    incomingCount[right],
                                    overlapLength
                                );

                            if (
                                leftFallback !=
                                rightFallback
                            ) {
                                return
                                    leftFallback >
                                    rightFallback;
                            }

                            return left > right;
                        }
                    );
                }

                while (
                    !availableSources.empty() &&
                    !availableTargets.empty()
                ) {
                    int sourceIndex;
                    int targetIndex;

                    if (attempt == 0) {
                        sourceIndex =
                            static_cast<int>(
                                availableSources.size()
                            ) - 1;

                        targetIndex =
                            static_cast<int>(
                                availableTargets.size()
                            ) - 1;
                    } else {
                        sourceIndex = random.index(
                            static_cast<int>(
                                availableSources.size()
                            )
                        );

                        targetIndex = random.index(
                            static_cast<int>(
                                availableTargets.size()
                            )
                        );
                    }

                    int source =
                        availableSources[sourceIndex];

                    if (
                        chains.find(source) ==
                        chains.find(
                            availableTargets[targetIndex]
                        )
                    ) {
                        if (availableTargets.size() == 1) {
                            availableSources[sourceIndex] =
                                availableSources.back();

                            availableSources.pop_back();
                            continue;
                        }

                        targetIndex =
                            (targetIndex + 1) %
                            static_cast<int>(
                                availableTargets.size()
                            );
                    }

                    int target =
                        availableTargets[targetIndex];

                    // Защитный поиск: обычно этот цикл не выполняется.
                    if (
                        chains.find(source) ==
                        chains.find(target)
                    ) {
                        bool found = false;

                        for (int i = 0;
                             i <
                             static_cast<int>(
                                 availableTargets.size()
                             );
                             ++i) {
                            if (
                                chains.find(source) !=
                                chains.find(
                                    availableTargets[i]
                                )
                            ) {
                                targetIndex = i;
                                target =
                                    availableTargets[i];
                                found = true;
                                break;
                            }
                        }

                        if (!found) {
                            availableSources[sourceIndex] =
                                availableSources.back();

                            availableSources.pop_back();
                            continue;
                        }
                    }

                    next[source] = target;
                    previous[target] = source;

                    overlapLengthAfter[source] =
                        static_cast<uint16_t>(
                            overlapLength
                        );

                    chains.unite(source, target);
                    savedLength += overlapLength;

                    availableSources[sourceIndex] =
                        availableSources.back();

                    availableSources.pop_back();

                    availableTargets[targetIndex] =
                        availableTargets.back();

                    availableTargets.pop_back();
                }

                suffixIndex = nextSuffixIndex;
                prefixIndex = nextPrefixIndex;
            }
        }

        if (savedLength > bestSavedLength) {
            bestSavedLength = savedLength;
            bestNext = move(next);
            bestPrevious = move(previous);
            bestOverlapLength =
                move(overlapLengthAfter);
        }
    }

    string answer;

    answer.reserve(
        static_cast<size_t>(
            activeTotalLength - bestSavedLength
        )
    );

    vector<int> heads;

    for (int i = 0; i < activeCount; ++i) {
        if (bestPrevious[i] == -1) {
            heads.push_back(i);
        }
    }

    sort(
        heads.begin(),
        heads.end(),
        [&](int left, int right) {
            return active[left] < active[right];
        }
    );

    bool firstComponent = true;

    for (int head : heads) {
        int current = head;

        if (firstComponent) {
            answer += strings[active[current]];
            firstComponent = false;
        } else {
            answer += strings[active[current]];
        }

        while (bestNext[current] != -1) {
            int next = bestNext[current];

            answer.append(
                strings[active[next]],
                bestOverlapLength[current],
                string::npos
            );

            current = next;
        }
    }

    cout << answer << '\n';
    return 0;
}

Оценка сложности

Обозначим через $S$ суммарную длину входных строк.

построение суффиксного массива: $O(S\log S)$ ;
построение и сортировка групп перекрытий: примерно $O(S\log n)$ ;
один жадный запуск: $O(S+n\alpha(n))$ ;
память: $O(S)$ .

На максимальном случайном тесте с суммарной длиной около двух миллионов символов эта реализация использует около 90 МБ памяти. На приведённом примере она выводит авторский вариант:

text
aaabbabaabaab

Answer 3

Обозначим два способа установки:

A — поставить кресло в начало;
B — поставить после предыдущего номера.

1. Откуда берутся локальные минимумы

Каждая операция A начинает новый блок, а последующие операции B продолжают его. В итоговом ряду блоки расположены в обратном порядке, а внутри каждого блока номера возрастают.

Локальный минимум возникает ровно тогда, когда некоторый непервый блок содержит хотя бы два элемента. Это эквивалентно соседней паре решений

text
B A

Следовательно, нужно выбрать последовательность A/B, минимизируя количество переходов B → A при ограничении на стоимость.

2. Выпуклость зависимости стоимости

Пусть

F(k)=\text{минимальная стоимость при не более чем }k \text{ переходах }B\to A.

Последовательность $F(k)$ дискретно выпукла: величины

F(k-1)-F(k)

не возрастают.

Это можно увидеть, если взять вариант «везде B» и рассматривать позиции, на которых выбрано A. Они образуют непересекающиеся отрезки. Каждый новый отрезок, кроме начинающегося в l, соответствует одному переходу B → A. Получается стандартная задача о максимальном весе нескольких непересекающихся подотрезков, чья оптимальная прибыль является вогнутой по числу отрезков.

Благодаря выпуклости применим параметрический поиск. Для целого $\lambda$ минимизируем

\text{cost}+\lambda\cdot k.

3. Матрицы переходов

Состояние — последнее выбранное действие: A или B.

Для позиции $i$ матрица имеет четыре перехода:

Предыдущее	Новое	Стоимость	Новые минимумы
A	A	$a_i$	0
A	B	$b_i$	0
B	A	$a_i$	1
B	B	$b_i$	0

Перед позицией l считаем состояние равным A, поэтому первая операция не создаёт локального минимума.

В каждой ячейке матрицы храним нижнюю выпуклую оболочку точек

(k,\text{cost}).

Матрицы соседних отрезков перемножаются:

стоимости и количества минимумов складываются — сумма Минковского оболочек;
выбирается промежуточное состояние — объединение и построение новой нижней оболочки.

Матрицы хранятся в дереве отрезков.

Для фиксированного $\lambda$ оптимальная точка оболочки находится бинарным поиском по наклонам.

Сложность

построение: $O(n\log n)$ ;
один запрос: $O(\log W\cdot\log^2 n)$ , где $W\le 5\cdot10^{12}$ ;
память: $O(n\log n)$ .

cpp
#include <algorithm>
#include <array>
#include <climits>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;
using int128 = __int128_t;

static constexpr int64 INF = 4'000'000'000'000'000'000LL;

struct Point {
    int minima;
    int64 cost;
};

using Hull = vector<Point>;

// Сравнение наклонов отрезков a1-a2 и b1-b2.
static int compareSlopes(
    const Point& a1,
    const Point& a2,
    const Point& b1,
    const Point& b2
) {
    const int64 deltaCostA = a2.cost - a1.cost;
    const int deltaMinimaA = a2.minima - a1.minima;

    const int64 deltaCostB = b2.cost - b1.cost;
    const int deltaMinimaB = b2.minima - b1.minima;

    const int128 left =
        static_cast<int128>(deltaCostA) * deltaMinimaB;

    const int128 right =
        static_cast<int128>(deltaCostB) * deltaMinimaA;

    if (left < right) {
        return -1;
    }

    if (left > right) {
        return 1;
    }

    return 0;
}

// Нижняя выпуклая оболочка суммы двух множеств точек.
//
// Если A и B уже являются выпуклыми цепочками,
// оболочка их суммы получается слиянием рёбер по наклонам.
static Hull minkowskiSum(const Hull& a, const Hull& b) {
    if (a.empty() || b.empty()) {
        return {};
    }

    Hull result;
    result.reserve(a.size() + b.size() - 1);

    Point current{
        a[0].minima + b[0].minima,
        a[0].cost + b[0].cost
    };

    result.push_back(current);

    size_t i = 1;
    size_t j = 1;

    while (i < a.size() || j < b.size()) {
        if (j == b.size()) {
            current.minima +=
                a[i].minima - a[i - 1].minima;

            current.cost +=
                a[i].cost - a[i - 1].cost;

            ++i;
        } else if (i == a.size()) {
            current.minima +=
                b[j].minima - b[j - 1].minima;

            current.cost +=
                b[j].cost - b[j - 1].cost;

            ++j;
        } else {
            const int comparison = compareSlopes(
                a[i - 1],
                a[i],
                b[j - 1],
                b[j]
            );

            if (comparison < 0) {
                current.minima +=
                    a[i].minima - a[i - 1].minima;

                current.cost +=
                    a[i].cost - a[i - 1].cost;

                ++i;
            } else if (comparison > 0) {
                current.minima +=
                    b[j].minima - b[j - 1].minima;

                current.cost +=
                    b[j].cost - b[j - 1].cost;

                ++j;
            } else {
                current.minima +=
                    a[i].minima - a[i - 1].minima +
                    b[j].minima - b[j - 1].minima;

                current.cost +=
                    a[i].cost - a[i - 1].cost +
                    b[j].cost - b[j - 1].cost;

                ++i;
                ++j;
            }
        }

        result.push_back(current);
    }

    return result;
}

// Нижняя выпуклая оболочка объединения двух оболочек.
static Hull uniteHulls(const Hull& a, const Hull& b) {
    vector<Point> merged;
    merged.reserve(a.size() + b.size());

    size_t i = 0;
    size_t j = 0;

    while (i < a.size() || j < b.size()) {
        if (
            j == b.size() ||
            (
                i < a.size() &&
                a[i].minima < b[j].minima
            )
        ) {
            merged.push_back(a[i++]);
        } else if (
            i == a.size() ||
            b[j].minima < a[i].minima
        ) {
            merged.push_back(b[j++]);
        } else {
            merged.push_back({
                a[i].minima,
                min(a[i].cost, b[j].cost)
            });

            ++i;
            ++j;
        }
    }

    // Удаляем доминируемые точки:
    // больше минимумов при не меньшей стоимости.
    vector<Point> useful;
    useful.reserve(merged.size());

    int64 bestCost = INF;

    for (const Point& point : merged) {
        if (point.cost < bestCost) {
            useful.push_back(point);
            bestCost = point.cost;
        }
    }

    Hull result;
    result.reserve(useful.size());

    for (const Point& point : useful) {
        while (result.size() >= 2) {
            const Point& first =
                result[result.size() - 2];

            const Point& second =
                result[result.size() - 1];

            const int128 left =
                static_cast<int128>(
                    second.cost - first.cost
                ) *
                (point.minima - second.minima);

            const int128 right =
                static_cast<int128>(
                    point.cost - second.cost
                ) *
                (second.minima - first.minima);

            // Наклоны должны строго возрастать.
            if (left >= right) {
                result.pop_back();
            } else {
                break;
            }
        }

        result.push_back(point);
    }

    return result;
}

struct HullMatrix {
    Hull cell[2][2];
};

static HullMatrix multiplyHullMatrices(
    const HullMatrix& left,
    const HullMatrix& right
) {
    HullMatrix result;

    for (int from = 0; from < 2; ++from) {
        for (int to = 0; to < 2; ++to) {
            Hull throughA = minkowskiSum(
                left.cell[from][0],
                right.cell[0][to]
            );

            Hull throughB = minkowskiSum(
                left.cell[from][1],
                right.cell[1][to]
            );

            result.cell[from][to] =
                uniteHulls(throughA, throughB);
        }
    }

    return result;
}

struct Evaluation {
    int64 penalizedCost;
    int minimumK;
    int maximumK;
};

// Найти все оптимальные точки для cost + lambda * k.
//
// minimumK и maximumK — крайние значения k,
// достигающие одинакового минимума.
static Evaluation evaluateHull(
    const Hull& hull,
    int64 lambda
) {
    if (hull.empty()) {
        return {
            INF,
            INT_MAX / 4,
            INT_MIN / 4
        };
    }

    const int size = static_cast<int>(hull.size());

    if (size == 1) {
        const Point& point = hull[0];

        return {
            point.cost +
                lambda * static_cast<int64>(point.minima),
            point.minima,
            point.minima
        };
    }

    auto edgeDelta = [&](int edge) -> int128 {
        return
            static_cast<int128>(
                hull[edge].cost -
                hull[edge - 1].cost
            ) +
            static_cast<int128>(lambda) *
            (
                hull[edge].minima -
                hull[edge - 1].minima
            );
    };

    // Первое ребро, после которого целевая функция
    // больше не убывает.
    int low = 1;
    int high = size;

    while (low < high) {
        const int middle = (low + high) / 2;

        if (edgeDelta(middle) >= 0) {
            high = middle;
        } else {
            low = middle + 1;
        }
    }

    const int firstNonNegative = low;

    if (firstNonNegative == size) {
        const Point& point = hull.back();

        return {
            point.cost +
                lambda * static_cast<int64>(point.minima),
            point.minima,
            point.minima
        };
    }

    if (edgeDelta(firstNonNegative) > 0) {
        const Point& point =
            hull[firstNonNegative - 1];

        return {
            point.cost +
                lambda * static_cast<int64>(point.minima),
            point.minima,
            point.minima
        };
    }

    // Есть несколько последовательных точек,
    // лежащих на прямой наклона -lambda.
    low = firstNonNegative;
    high = size;

    while (low < high) {
        const int middle = (low + high) / 2;

        if (edgeDelta(middle) > 0) {
            high = middle;
        } else {
            low = middle + 1;
        }
    }

    const int firstPositive = low;
    const int leftVertex = firstNonNegative - 1;
    const int rightVertex = firstPositive - 1;

    const int64 value =
        hull[leftVertex].cost +
        lambda *
            static_cast<int64>(
                hull[leftVertex].minima
            );

    return {
        value,
        hull[leftVertex].minima,
        hull[rightVertex].minima
    };
}

static Evaluation addEvaluations(
    const Evaluation& first,
    const Evaluation& second
) {
    if (
        first.penalizedCost >= INF / 2 ||
        second.penalizedCost >= INF / 2
    ) {
        return {
            INF,
            INT_MAX / 4,
            INT_MIN / 4
        };
    }

    return {
        first.penalizedCost +
            second.penalizedCost,

        first.minimumK +
            second.minimumK,

        first.maximumK +
            second.maximumK
    };
}

static Evaluation chooseBetter(
    const Evaluation& first,
    const Evaluation& second
) {
    if (
        first.penalizedCost <
        second.penalizedCost
    ) {
        return first;
    }

    if (
        second.penalizedCost <
        first.penalizedCost
    ) {
        return second;
    }

    if (first.penalizedCost >= INF / 2) {
        return first;
    }

    return {
        first.penalizedCost,
        min(first.minimumK, second.minimumK),
        max(first.maximumK, second.maximumK)
    };
}

struct EvaluatedMatrix {
    Evaluation cell[2][2];
};

static EvaluatedMatrix identityEvaluatedMatrix() {
    EvaluatedMatrix result;

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (i == j) {
                result.cell[i][j] = {0, 0, 0};
            } else {
                result.cell[i][j] = {
                    INF,
                    INT_MAX / 4,
                    INT_MIN / 4
                };
            }
        }
    }

    return result;
}

static EvaluatedMatrix evaluateMatrix(
    const HullMatrix& matrix,
    int64 lambda
) {
    EvaluatedMatrix result;

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            result.cell[i][j] =
                evaluateHull(
                    matrix.cell[i][j],
                    lambda
                );
        }
    }

    return result;
}

static EvaluatedMatrix multiplyEvaluatedMatrices(
    const EvaluatedMatrix& left,
    const EvaluatedMatrix& right
) {
    EvaluatedMatrix result;

    for (int from = 0; from < 2; ++from) {
        for (int to = 0; to < 2; ++to) {
            const Evaluation throughA =
                addEvaluations(
                    left.cell[from][0],
                    right.cell[0][to]
                );

            const Evaluation throughB =
                addEvaluations(
                    left.cell[from][1],
                    right.cell[1][to]
                );

            result.cell[from][to] =
                chooseBetter(throughA, throughB);
        }
    }

    return result;
}

class SegmentTree {
public:
    SegmentTree(
        const vector<int64>& costA,
        const vector<int64>& costB
    ) {
        const int n = static_cast<int>(costA.size());

        size_ = 1;

        while (size_ < n) {
            size_ <<= 1;
        }

        tree_.resize(2 * size_);

        for (int i = 0; i < n; ++i) {
            HullMatrix matrix;

            // 0 = A, 1 = B.
            matrix.cell[0][0] = {{0, costA[i]}};
            matrix.cell[0][1] = {{0, costB[i]}};
            matrix.cell[1][0] = {{1, costA[i]}};
            matrix.cell[1][1] = {{0, costB[i]}};

            tree_[size_ + i] = std::move(matrix);
        }

        // Нейтральные листья.
        for (int i = n; i < size_; ++i) {
            HullMatrix identity;
            identity.cell[0][0] = {{0, 0}};
            identity.cell[1][1] = {{0, 0}};

            tree_[size_ + i] = std::move(identity);
        }

        for (int vertex = size_ - 1; vertex > 0; --vertex) {
            tree_[vertex] = multiplyHullMatrices(
                tree_[2 * vertex],
                tree_[2 * vertex + 1]
            );
        }
    }

    Evaluation evaluateRange(
        int left,
        int right,
        int64 lambda
    ) const {
        EvaluatedMatrix leftProduct =
            identityEvaluatedMatrix();

        EvaluatedMatrix rightProduct =
            identityEvaluatedMatrix();

        left += size_;
        right += size_ + 1;

        while (left < right) {
            if (left & 1) {
                leftProduct =
                    multiplyEvaluatedMatrices(
                        leftProduct,
                        evaluateMatrix(
                            tree_[left],
                            lambda
                        )
                    );

                ++left;
            }

            if (right & 1) {
                --right;

                rightProduct =
                    multiplyEvaluatedMatrices(
                        evaluateMatrix(
                            tree_[right],
                            lambda
                        ),
                        rightProduct
                    );
            }

            left >>= 1;
            right >>= 1;
        }

        const EvaluatedMatrix result =
            multiplyEvaluatedMatrices(
                leftProduct,
                rightProduct
            );

        // Перед первой позицией виртуально стоит A.
        // Конечное состояние может быть любым.
        return chooseBetter(
            result.cell[0][0],
            result.cell[0][1]
        );
    }

private:
    int size_ = 1;
    vector<HullMatrix> tree_;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int queryCount;

    cin >> n >> queryCount;

    vector<int64> costA(n);
    vector<int64> costB(n);

    for (int64& value : costA) {
        cin >> value;
    }

    for (int64& value : costB) {
        cin >> value;
    }

    SegmentTree tree(costA, costB);

    int64 globalUpperBound = 0;

    for (int i = 0; i < n; ++i) {
        globalUpperBound += max(costA[i], costB[i]);
    }

    // При таком штрафе любой вариант с хотя бы
    // одним минимумом хуже некоторого варианта с нулём.
    const int64 maximumLambda =
        globalUpperBound + 1;

    while (queryCount--) {
        int left;
        int right;
        int64 budget;

        cin >> left >> right >> budget;

        --left;
        --right;

        // lambda = 0 даёт минимально возможную стоимость
        // без ограничения на число минимумов.
        const Evaluation cheapest =
            tree.evaluateRange(left, right, 0);

        if (cheapest.penalizedCost > budget) {
            cout << -1 << '\n';
            continue;
        }

        // Проверяем, можно ли обойтись без минимумов.
        const Evaluation zeroCheck =
            tree.evaluateRange(
                left,
                right,
                maximumLambda
            );

        const int64 zeroCheckRawCost =
            zeroCheck.penalizedCost -
            maximumLambda *
                static_cast<int64>(
                    zeroCheck.maximumK
                );

        if (zeroCheckRawCost <= budget) {
            cout << 0 << '\n';
            continue;
        }

        // Ищем максимальный lambda, при котором
        // наиболее дешёвая по исходной стоимости
        // оптимальная точка ещё укладывается в бюджет.
        int64 low = 0;
        int64 high = maximumLambda;

        while (high - low > 1) {
            const int64 middle =
                low + (high - low) / 2;

            const Evaluation evaluation =
                tree.evaluateRange(
                    left,
                    right,
                    middle
                );

            const int64 rawCost =
                evaluation.penalizedCost -
                middle *
                    static_cast<int64>(
                        evaluation.maximumK
                    );

            if (rawCost <= budget) {
                low = middle;
            } else {
                high = middle;
            }
        }

        const Evaluation evaluation =
            tree.evaluateRange(
                left,
                right,
                low
            );

        const int64 costAtMinimumK =
            evaluation.penalizedCost -
            low *
                static_cast<int64>(
                    evaluation.minimumK
                );

        int answer;

        if (costAtMinimumK <= budget) {
            answer = evaluation.minimumK;
        } else {
            // На всём интервале оптимальных k стоимость
            // уменьшается ровно на low при увеличении k на 1.
            const int64 requiredSaving =
                costAtMinimumK - budget;

            const int additional =
                static_cast<int>(
                    (requiredSaving + low - 1) / low
                );

            answer =
                evaluation.minimumK +
                additional;
        }

        cout << answer << '\n';
    }

    return 0;
}

Answer 4

Наблюдения

Пусть робот находится в клетке $(i,j)$ , уже получив увеличение параметра от этой клетки.

До неё он посетил ровно $i+j-1$ клеток. Каждая посещённая клетка увеличила либо $k$ , либо $p$ , поэтому

k+p=1+(i+j-1)=i+j,

то есть

k=i+j-p.

Значит, если известно текущее значение $p$ , значение $k$ восстанавливается однозначно.

Когда робот покидает строку

Пусть из $(i,j)$ он идёт вниз. После этого в строку $i$ он уже никогда не вернётся.

Текущая щётка очищает в этой строке клетки до столбца

j+k-1.

Более ранние положения робота не могли очистить клетки правее: правый край квадрата щётки вдоль пути только увеличивается. Будущие положения находятся ниже и уже не могут очистить строку $i$ .

Следовательно, все изначально грязные клетки строки $i$ , находящиеся правее $j+k-1$ , необходимо очистить лазером строки. Это возможно тогда и только тогда, когда их количество не превосходит $p$ .

Аналогично, при ходе вправо робот навсегда покидает столбец $j$ . Число грязных клеток ниже строки $i+k-1$ должно быть не больше $p$ .

Почему достаточно хранить только максимальное $p$

Для одной клетки могут существовать разные пути с разными значениями $p$ .

Рассмотрим проверку выхода из строки. При увеличении $p$ на единицу размер щётки $k$ уменьшается на единицу. Поэтому необработанный хвост строки увеличивается максимум на одну клетку, но и мощность лазера увеличивается на единицу.

Таким образом, если переход был возможен при некотором $p$ , то он возможен и при любом большем $p$ .

То же верно для выхода из столбца. Поэтому для каждой клетки достаточно хранить только максимальное достижимое значение $p$ .

Получается обычная динамика по монотонным путям.

cpp
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <string>
#include <vector>

class FastInput {
    static constexpr int BUFFER_SIZE = 1 << 20;

    char buffer_[BUFFER_SIZE];
    int position_ = 0;
    int length_ = 0;

    inline char getChar() {
        if (position_ == length_) {
            length_ = static_cast<int>(
                std::fread(buffer_, 1, BUFFER_SIZE, stdin)
            );
            position_ = 0;

            if (length_ == 0) {
                return '\0';
            }
        }

        return buffer_[position_++];
    }

public:
    int readInt() {
        char c = getChar();

        while (c <= ' ') {
            c = getChar();
        }

        int value = 0;

        while (c >= '0' && c <= '9') {
            value = value * 10 + (c - '0');
            c = getChar();
        }

        return value;
    }

    void readRow(char* destination, int length) {
        char c = getChar();

        while (c <= ' ') {
            c = getChar();
        }

        destination[0] = c;

        for (int i = 1; i < length; ++i) {
            destination[i] = getChar();
        }
    }
};

static inline bool isDirty(char cell) {
    return cell == '3' || cell == '4';
}

static inline int increasesPower(char cell) {
    return cell == '2' || cell == '4';
}

int main() {
    FastInput input;

    const int testCount = input.readInt();

    std::string output;
    output.reserve(static_cast<std::size_t>(testCount) * 4);

    for (int test = 0; test < testCount; ++test) {
        const int n = input.readInt();
        const int m = input.readInt();
        const int cellCount = n * m;

        std::vector<char> grid(cellCount);

        for (int i = 0; i < n; ++i) {
            input.readRow(grid.data() + i * m, m);
        }

        /*
         * columnSuffix[i * m + j] —
         * число изначально грязных клеток в столбце j
         * на строках i, i + 1, ..., n - 1.
         *
         * Максимальное значение равно n <= 3000,
         * поэтому uint16_t достаточно.
         */
        std::vector<std::uint16_t> columnSuffix(cellCount);
        std::vector<std::uint16_t> columnCount(m, 0);

        for (int i = n - 1; i >= 0; --i) {
            const int rowBase = i * m;

            for (int j = 0; j < m; ++j) {
                columnCount[j] += static_cast<std::uint16_t>(
                    isDirty(grid[rowBase + j])
                );

                columnSuffix[rowBase + j] = columnCount[j];
            }
        }

        /*
         * current[j] — максимальная мощность p,
         * с которой можно оказаться в текущей строке
         * в столбце j.
         */
        std::vector<int> current(m, -1);
        std::vector<int> next(m, -1);

        // Счётчики грязных клеток в суффиксах текущей строки.
        std::vector<std::uint16_t> rowSuffix(m + 1, 0);

        // Эффект клетки (1, 1) применяется сразу.
        current[0] = increasesPower(grid[0]);

        for (int i = 0; i < n; ++i) {
            std::fill(next.begin(), next.end(), -1);

            const int rowBase = i * m;

            rowSuffix[m] = 0;

            for (int j = m - 1; j >= 0; --j) {
                rowSuffix[j] = static_cast<std::uint16_t>(
                    rowSuffix[j + 1] +
                    isDirty(grid[rowBase + j])
                );
            }

            for (int j = 0; j < m; ++j) {
                const int power = current[j];

                if (power < 0) {
                    continue;
                }

                /*
                 * В нулевой индексации посещено i + j + 1 клеток:
                 *
                 * k = 1 + количество клеток, увеличивших k
                 *   = 1 + (i + j + 1 - p)
                 *   = i + j + 2 - p.
                 */
                const int brushSize = i + j + 2 - power;

                /*
                 * Ход вправо.
                 *
                 * Мы навсегда покидаем столбец j.
                 * Щётка доходит до строки
                 * bottom = i + brushSize - 1.
                 */
                if (j + 1 < m) {
                    const int bottom = i + brushSize - 1;

                    int dirtyBelow = 0;

                    if (bottom + 1 < n) {
                        dirtyBelow =
                            columnSuffix[(bottom + 1) * m + j];
                    }

                    if (dirtyBelow <= power) {
                        const int newPower =
                            power +
                            increasesPower(grid[rowBase + j + 1]);

                        if (newPower > current[j + 1]) {
                            current[j + 1] = newPower;
                        }
                    }
                }

                /*
                 * Ход вниз.
                 *
                 * Мы навсегда покидаем строку i.
                 * Щётка доходит до столбца
                 * right = j + brushSize - 1.
                 */
                if (i + 1 < n) {
                    const int right = j + brushSize - 1;

                    const int firstUncovered =
                        std::min(m, right + 1);

                    const int dirtyRight =
                        rowSuffix[firstUncovered];

                    if (dirtyRight <= power) {
                        const int newPower =
                            power +
                            increasesPower(
                                grid[rowBase + m + j]
                            );

                        if (newPower > next[j]) {
                            next[j] = newPower;
                        }
                    }
                }
            }

            if (i + 1 < n) {
                current.swap(next);
            }
        }

        output += current[m - 1] >= 0
            ? "Yes\n"
            : "No\n";
    }

    std::fwrite(
        output.data(),
        1,
        output.size(),
        stdout
    );

    return 0;
}

Сложность

Для каждого теста:

O(nm)

по времени и

O(nm)

по памяти. Основной массив суффиксов столбцов занимает $2nm$ байт.

Кодерун съездил в отпуск и привёз множество распеч...

问题

思考

回答

Идея

GNU C++20

问题

思考

回答

Оценка сложности

问题

Python

Python

思考

回答

1. Откуда берутся локальные минимумы

2. Выпуклость зависимости стоимости

3. Матрицы переходов

Сложность

问题

Python

Python

思考

回答

Наблюдения

Когда робот покидает строку

Почему достаточно хранить только максимальное $p$

Сложность

分享这个问答

问题

思考

回答

Идея

GNU C++20

问题

思考

回答

Оценка сложности

问题

Python

Python

思考

回答

1. Откуда берутся локальные минимумы

2. Выпуклость зависимости стоимости

3. Матрицы переходов

Сложность

问题

Python

Python

思考

回答

Наблюдения

Когда робот покидает строку

Почему достаточно хранить только максимальное ppp

Сложность

分享这个问答

Почему достаточно хранить только максимальное $p$