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

• 問題: No.2465 Dilated Water Simulation
• ユーザー: butsurizuki
• 提出日時: 2026-07-22 02:40:41
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 106 ms / 2,000 ms
• コード長: 8,088 bytes
• コンパイル時間: 2,206 ms
• コンパイル使用メモリ: 340,848 KB
• 実行使用メモリ: 20,608 KB
• 最終ジャッジ日時: 2026-07-22 02:40:48
• 合計ジャッジ時間: 6,637 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

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

using i64 = long long;

static i64 mul64(i64 a, i64 b) {
    // 実際の積は高々 sum(V_i) <= 2e14 だが、
    // 乗算そのものも安全にするため int128 を使う。
    return static_cast<i64>(static_cast<__int128>(a) * b);
}

struct Fenwick {
    int n;
    vector<i64> bit;

    explicit Fenwick(int n = 0) : n(n), bit(n + 1, 0) {}

    void add(int i, i64 delta) {
        for (; i <= n; i += i & -i) bit[i] += delta;
    }

    i64 sum_prefix(int i) const {
        i64 result = 0;
        for (; i > 0; i -= i & -i) result += bit[i];
        return result;
    }

    // sum_prefix(i) >= target となる最小の i。
    // 1 <= target <= sum_prefix(n) を仮定する。
    int lower_bound(i64 target) const {
        int index = 0;
        i64 accumulated = 0;

        int step = 1;
        while ((step << 1) <= n) step <<= 1;

        for (; step > 0; step >>= 1) {
            int next = index + step;
            if (next <= n && accumulated + bit[next] < target) {
                index = next;
                accumulated += bit[next];
            }
        }

        return index + 1;
    }
};

struct Run {
    i64 height;
    i64 length;
};

// ランレングス圧縮された列。
// vector の末尾が列の先頭になるよう、逆向きに保持する。
class RunSequence {
    vector<Run> runs;

    Fenwick length_fenwick;
    Fenwick weight_fenwick;

    i64 total_length = 0;
    i64 total_weight = 0;

    void change_front_length(i64 delta) {
        int index = static_cast<int>(runs.size());
        i64 height = runs.back().height;

        runs.back().length += delta;

        length_fenwick.add(index, delta);
        weight_fenwick.add(index, mul64(height, delta));

        total_length += delta;
        total_weight += mul64(height, delta);
    }

    void pop_front_run() {
        int index = static_cast<int>(runs.size());
        Run run = runs.back();

        length_fenwick.add(index, -run.length);
        weight_fenwick.add(
            index,
            -mul64(run.height, run.length)
        );

        total_length -= run.length;
        total_weight -= mul64(run.height, run.length);

        runs.pop_back();
    }

public:
    explicit RunSequence(int maximum_runs)
        : length_fenwick(maximum_runs),
          weight_fenwick(maximum_runs) {
        runs.reserve(maximum_runs);
    }

    bool empty() const {
        return runs.empty();
    }

    Run front_run() const {
        return runs.back();
    }

    void consume_front(i64 count) {
        assert(!runs.empty());
        assert(1 <= count && count <= runs.back().length);

        if (count == runs.back().length) {
            pop_front_run();
        } else {
            change_front_length(-count);
        }
    }

    // 列の先頭に height を length 個追加する。
    void push_front(i64 height, i64 length) {
        if (height == 0 || length == 0) return;

        if (!runs.empty() && runs.back().height == height) {
            change_front_length(length);
            return;
        }

        runs.push_back({height, length});

        int index = static_cast<int>(runs.size());

        length_fenwick.add(index, length);
        weight_fenwick.add(
            index,
            mul64(height, length)
        );

        total_length += length;
        total_weight += mul64(height, length);
    }

    // 列の先頭 q 項の和。
    i64 prefix_sum(i64 q) const {
        if (q <= 0 || total_length == 0) return 0;
        if (q >= total_length) return total_weight;

        // vector 内では列が逆向きなので、
        // vector 側の先頭 total_length-q 項を除外する。
        i64 excluded_length = total_length - q;

        int index =
            length_fenwick.lower_bound(excluded_length);

        i64 length_before =
            length_fenwick.sum_prefix(index - 1);

        i64 weight_before =
            weight_fenwick.sum_prefix(index - 1);

        i64 take = excluded_length - length_before;

        i64 excluded_weight =
            weight_before
            + mul64(runs[index - 1].height, take);

        return total_weight - excluded_weight;
    }
};

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

    int L;
    cin >> L;

    vector<i64> V(L);
    for (i64& value : V) cin >> value;

    i64 N;
    cin >> N;

    const i64 minimum_capacity =
        *min_element(V.begin(), V.end());

    // 共通部分 m を引いた容量。
    vector<i64> capacity(L);

    for (int i = 0; i < L; ++i) {
        capacity[i] = V[i] - minimum_capacity;
    }

    const i64 complete_cycles = N / L;
    const int remaining_operations =
        static_cast<int>(N % L);

    vector<i64> answer(L, 0);

    const i64 water = capacity[0];

    if (water == 0) {
        // 共通部分の水しか存在しない。
        answer[0] = minimum_capacity;
    } else {
        // 最初の容量 0 の容器。
        int K = 0;
        while (K < L && capacity[K] > 0) ++K;

        assert(1 <= K && K < L);

        vector<i64> prefix_minimum(K);

        prefix_minimum[0] = capacity[0];

        for (int i = 1; i < K; ++i) {
            prefix_minimum[i] =
                min(prefix_minimum[i - 1], capacity[i]);
        }

        // prefix_at_q[i]
        //   = lambda^(i) の先頭 complete_cycles 項の和。
        // lambda^(K) は 0 列。
        vector<i64> prefix_at_q(K + 1, 0);

        // 現在 lambda^(i+1) を保持する。
        // 1 容器につき高々 2 区間増える。
        RunSequence sequence(2 * L + 10);

        for (int i = K - 1; i >= 1; --i) {
            const i64 g = prefix_minimum[i];

            i64 remainder = capacity[i];
            i64 full_terms = 0;

            // remainder >= g の間は出力が g。
            while (!sequence.empty() && remainder >= g) {
                Run run = sequence.front_run();

                assert(run.height <= g);

                i64 take;

                if (run.height == g) {
                    // remainder は減らない。
                    take = run.length;
                } else {
                    const i64 decrease = g - run.height;

                    take = min(
                        run.length,
                        (remainder - g) / decrease + 1
                    );
                }

                full_terms += take;

                remainder -=
                    mul64(take, g - run.height);

                sequence.consume_front(take);

                if (take < run.length) {
                    // 最大限消費したので remainder < g。
                    break;
                }
            }

            // 有限列の後ろはすべて 0。
            if (sequence.empty() && remainder >= g) {
                full_terms += remainder / g;
                remainder %= g;
            }

            // 新しい列は
            // [g が full_terms 個], [remainder], [古い列の残り]
            sequence.push_front(remainder, 1);
            sequence.push_front(g, full_terms);

            prefix_at_q[i] =
                sequence.prefix_sum(complete_cycles);
        }

        auto cap_by_water = [&](i64 value) -> i64 {
            return min(water, value);
        };

        answer[0] =
            water
            - cap_by_water(prefix_at_q[1])
            + minimum_capacity;

        for (int i = 1; i < K; ++i) {
            answer[i] =
                cap_by_water(prefix_at_q[i])
                - cap_by_water(prefix_at_q[i + 1]);
        }
    }

    // 最後の不完全な 1 周を直接処理する。
    // remaining_operations < L なので折り返し辺は含まれない。
    for (int i = 0; i < remaining_operations; ++i) {
        i64 moved = min(
            answer[i],
            V[i + 1] - answer[i + 1]
        );

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

    for (int i = 0; i < L; ++i) {
        if (i != 0) cout << ' ';
        cout << answer[i];
    }

    cout << '\n';
}