제출 #1292574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292574		green_gold_dog	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	62 ms	27428 KiB

Main

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

struct Block {
    long long color;
    int L, R;
};

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

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    vector<Block> blocks;
    blocks.reserve(N);

    // Для каждого цвета: стек индексов блоков с этим цветом
    unordered_map<long long, vector<int>> pos;
    pos.reserve(N * 2);

    for (int i = 1; i <= N; ++i) {
        long long c = A[i];

        if (blocks.empty()) {
            // Первый камень
            blocks.push_back({c, i, i});
            pos[c].push_back(0); // индекс блока 0
            continue;
        }

        int tail = (int)blocks.size() - 1;
        if (blocks[tail].color == c) {
            // Продлеваем последний блок
            blocks[tail].R = i;
            continue;
        }

        // Добавляем новый блок для камня i
        blocks.push_back({c, i, i});
        int new_idx = (int)blocks.size() - 1;
        auto &st = pos[c];
        st.push_back(new_idx);

        // Проверяем, был ли цвет c раньше до камня i
        if ((int)st.size() >= 2) {
            int prev_block_idx = st[(int)st.size() - 2]; // блок с последним вхождением c до i
            int old_tail = new_idx;

            // Удаляем все блоки после prev_block_idx (суффикс)
            for (int x = old_tail; x > prev_block_idx; --x) {
                long long colx = blocks[x].color;
                auto &stx = pos[colx];
                if (!stx.empty() && stx.back() == x) {
                    stx.pop_back();
                }
            }

            // Сжимаем массив блоков до prev_block_idx + 1
            blocks.resize(prev_block_idx + 1);
            // Расширяем этот блок до позиции i
            blocks[prev_block_idx].R = i;
            // В стеке цвета c теперь последний блок — prev_block_idx (он и должен быть последним)
        }
    }

    // Восстанавливаем итоговые цвета по блокам
    vector<long long> ans(N + 1);
    for (const auto &b : blocks) {
        for (int i = b.L; i <= b.R; ++i) {
            ans[i] = b.color;
        }
    }

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40