#1172426 (C++23) No.2465 Dilated Water Simulation

• 問題: No.2465 Dilated Water Simulation
• ユーザー: butsurizuki
• 提出日時: 2026-07-22 02:31:38
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 36 ms / 2,000 ms
• コード長: 7,008 bytes
• コンパイル時間: 2,426 ms
• コンパイル使用メモリ: 340,316 KB
• 実行使用メモリ: 17,408 KB
• 最終ジャッジ日時: 2026-07-22 02:31:45
• 合計ジャッジ時間: 6,687 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

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

using int64 = long long;
using i128 = __int128_t;

struct Run {
    int64 height;       // この区間での流量
    int64 length;       // 継続日数
    int64 pref_length;  // vector の先頭からの累積日数
    int64 pref_sum;     // vector の先頭からの累積流量
};

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

    int L;
    cin >> L;

    vector<int64> V(L);
    for (int64& x : V) cin >> x;

    int64 N;
    cin >> N;

    const int64 cycles = N / L;
    const int rem_ops = int(N % L);

    const auto min_it = min_element(V.begin(), V.end());
    const int64 base = *min_it;
    const int p = int(min_it - V.begin());

    vector<int64> ans(L, 0);

    /*
     * p は最初に最小容量が現れる位置。
     * 残りの水は 0,1,...,p-1 にしか存在できない。
     */
    if (p > 0) {
        vector<int64> U(p), bottleneck(p);

        for (int i = 0; i < p; ++i) {
            U[i] = V[i] - base;
        }

        bottleneck[0] = U[0];
        for (int i = 1; i < p; ++i) {
            bottleneck[i] = min(bottleneck[i - 1], U[i]);
        }

        /*
         * 流量列のランレングス表現。
         *
         * 時間順とは逆向きに保持する。
         * st.back() が最も早い時刻の区間。
         */
        vector<Run> st;
        st.reserve(3 * p + 5);

        auto push_run = [&](int64 height, int64 length) {
            if (length <= 0) return;

            const int64 old_length =
                st.empty() ? 0 : st.back().pref_length;
            const int64 old_sum =
                st.empty() ? 0 : st.back().pref_sum;

            const int64 add =
                (int64)((i128)height * length);

            st.push_back({
                height,
                length,
                old_length + length,
                old_sum + add
            });
        };

        auto pop_run = [&]() -> pair<int64, int64> {
            Run r = st.back();
            st.pop_back();
            return {r.height, r.length};
        };

        /*
         * 時間順で先頭 k 日分の流量和を返す。
         *
         * vector 内では時間が逆向きなので、
         * vector の末尾側が時間順の先頭に対応する。
         */
        auto time_prefix_sum = [&](int64 k) -> int64 {
            if (k <= 0 || st.empty()) return 0;

            const int64 total_length = st.back().pref_length;
            const int64 total_sum = st.back().pref_sum;

            if (k >= total_length) {
                return total_sum;
            }

            /*
             * vector の先頭側から total_length-k 日分を除く。
             */
            const int64 cut = total_length - k;

            int lo = 0;
            int hi = (int)st.size();

            while (lo < hi) {
                const int mid = (lo + hi) / 2;

                if (st[mid].pref_length >= cut) {
                    hi = mid;
                } else {
                    lo = mid + 1;
                }
            }

            const int idx = lo;

            const int64 prev_length =
                idx == 0 ? 0 : st[idx - 1].pref_length;
            const int64 prev_sum =
                idx == 0 ? 0 : st[idx - 1].pref_sum;

            const int64 removed =
                prev_sum
                + (int64)((i128)(cut - prev_length)
                          * st[idx].height);

            return total_sum - removed;
        };

        /*
         * cap[i] は、毎ラウンド容器 0 を補充する過程での
         * K ラウンド後の容器 i の水量。
         */
        vector<int64> cap(p, 0);

        /*
         * 現在の st が A_{i+1} を表しているとき、
         * A_i に変換する。
         */
        for (int i = p - 1; i >= 1; --i) {
            const int64 downstream_sum =
                time_prefix_sum(cycles);

            const int64 g = bottleneck[i];

            int64 free_space = U[i];
            int64 day = 1;

            /*
             * free_space >= g の間は流入量が g。
             * 下流流量が h なら、空き容量は毎日 g-h 減る。
             */
            while (!st.empty() && free_space >= g) {
                auto [h, length] = pop_run();

                if (h == g) {
                    day += length;
                    continue;
                }

                const int64 decrease = g - h;

                /*
                 * 流入量 g を維持できる日数。
                 */
                const int64 full_days =
                    (free_space - g) / decrease + 1;

                if (full_days >= length) {
                    free_space -=
                        (int64)((i128)length * decrease);
                    day += length;
                } else {
                    free_space -=
                        (int64)((i128)full_days * decrease);
                    day += full_days;

                    /*
                     * 現在の下流区間の未処理部分。
                     */
                    push_run(h, length - full_days);
                    break;
                }
            }

            /*
             * 明示された下流列が終わった後は流量 0。
             */
            day += free_space / g;
            free_space %= g;

            /*
             * 新しい列は
             *
             *   g が day-1 日
             *   free_space が 1 日
             *   未処理の旧列
             *
             * の順。
             *
             * st.back() が最も早い区間なので、
             * 逆順に push する。
             */
            push_run(free_space, 1);
            push_run(g, day - 1);

            const int64 this_sum =
                time_prefix_sum(cycles);

            cap[i] = this_sum - downstream_sum;
        }

        /*
         * 容器 0 は、右側に行かなかった水をすべて受け持つ。
         */
        cap[0] = U[0];

        /*
         * 補助過程にある水のうち、最古の U[0] 単位だけを取る。
         * 古い水ほど右側にある。
         */
        int64 remaining_water = U[0];

        for (int i = p - 1; i >= 0; --i) {
            ans[i] = min(cap[i], remaining_water);
            remaining_water -= ans[i];
        }
    }

    /*
     * 完全な周回の後、基礎水は容器 0 に戻っている。
     */
    ans[0] += base;

    /*
     * 最後の未完の周回を直接実行する。
     * rem_ops < L なので、ここでは円環の折り返しは発生しない。
     */
    for (int i = 0; i < rem_ops; ++i) {
        const int64 moved =
            min(ans[i], V[i + 1] - ans[i + 1]);

        ans[i] -= moved;
        ans[i + 1] += moved;
    }

    for (int i = 0; i < L; ++i) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}