結果

問題 No.2988 Min-Plus Convolution Query
ユーザー tatyamtatyam
提出日時 2024-11-27 02:45:47
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 678 ms / 2,000 ms
コード長 5,204 bytes
コンパイル時間 2,954 ms
コンパイル使用メモリ 144,552 KB
実行使用メモリ 275,596 KB
最終ジャッジ日時 2024-12-12 23:30:33
合計ジャッジ時間 25,893 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 678 ms
270,472 KB
testcase_03 AC 633 ms
273,552 KB
testcase_04 AC 640 ms
271,496 KB
testcase_05 AC 43 ms
19,228 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 114 ms
85,464 KB
testcase_10 AC 36 ms
23,604 KB
testcase_11 AC 9 ms
6,816 KB
testcase_12 AC 29 ms
19,368 KB
testcase_13 AC 229 ms
118,180 KB
testcase_14 AC 35 ms
22,836 KB
testcase_15 AC 390 ms
196,636 KB
testcase_16 AC 577 ms
260,828 KB
testcase_17 AC 337 ms
184,320 KB
testcase_18 AC 334 ms
182,272 KB
testcase_19 AC 294 ms
174,076 KB
testcase_20 AC 590 ms
271,496 KB
testcase_21 AC 601 ms
273,672 KB
testcase_22 AC 637 ms
273,544 KB
testcase_23 AC 616 ms
275,596 KB
testcase_24 AC 584 ms
273,548 KB
testcase_25 AC 542 ms
269,584 KB
testcase_26 AC 544 ms
269,580 KB
testcase_27 AC 651 ms
273,548 KB
testcase_28 AC 628 ms
273,416 KB
testcase_29 AC 655 ms
273,548 KB
testcase_30 AC 593 ms
273,548 KB
testcase_31 AC 633 ms
273,544 KB
testcase_32 AC 2 ms
6,820 KB
testcase_33 AC 2 ms
6,816 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 2 ms
6,816 KB
testcase_36 AC 2 ms
6,816 KB
testcase_37 AC 2 ms
6,820 KB
testcase_38 AC 2 ms
6,820 KB
testcase_39 AC 2 ms
6,820 KB
testcase_40 AC 2 ms
6,816 KB
testcase_41 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 時間軸をセグ木状に分割統治 + SMAWK algorithm
#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
using P = pair<int, int>;
bool chmin(ll& a, ll b) { return a > b ? a = b, 1 : 0; }

char* buf;
ll buf_ind;
template<class T> struct small {
    typedef T value_type;
    small() {}
    template<class U> small(const U&) {}
    T* allocate(size_t n) {
        if (n & 7) {
            n &= -8;
            n += 8;
        }
        buf_ind -= n * sizeof(T);
        buf_ind &= 0 - alignof(T);
        assert(buf_ind >= 0);
        return (T*)(buf + buf_ind);
    }
    void deallocate(T*, size_t) {}
};
using V = vector<P, small<P>>;

int main() {
    buf_ind = 3 << 28;
    buf = (char*)malloc(buf_ind);
    cin.tie(0)->sync_with_stdio(0);

    ll N, Q;
    cin >> N >> Q;
    vector<ll> A(N), B(N);
    for (ll& x : A) cin >> x;
    for (ll& x : B) cin >> x;
    vector<array<ll, 3>> queries(Q);
    for (auto& [p, x, k] : queries) {
        cin >> p >> x >> k;
        p--;
        k -= 2;
    }

    // {L, R, i, a}
    vector<array<ll, 4>> A_range;
    {
        vector<ll> L(N);
        for (ll t = 0; t < Q; t++) {
            auto [p, x, k] = queries[t];
            A_range.push_back({L[p], t, p, A[p]});
            L[p] = t;
            A[p] = x;
        }
        for (ll i = 0; i < N; i++) A_range.push_back({L[i], Q, i, A[i]});
    }
    ranges::sort(A_range, {}, [](auto& x) { return x[2]; });
    vector<P> k_query;  // {k, t}
    for (ll t = 0; t < Q; t++) {
        auto [p, x, k] = queries[t];
        k_query.push_back({k, t});
    }
    ranges::sort(k_query);

    vector<V> A_seg(Q * 2), C_seg(Q * 2);
    for (auto [L, R, i, a] : A_range) {
        L += Q;
        R += Q;
        for (; L < R; L >>= 1, R >>= 1) {
            if (L & 1) A_seg[L++].push_back({i, a});
            if (R & 1) A_seg[--R].push_back({i, a});
        }
    }
    for (auto [k, t] : k_query) {
        ll i = t + Q;
        do C_seg[i].push_back({k, t});
        while (i >>= 1);
    }

    vector<ll> ans(Q, INF);
    auto solve = [&](const V& A, const V& C_) {
        if (A.empty() || C_.empty()) return;

        auto C = begin(C_) - 1;
        static V A_dfs[20];
        static vector<int> idx;
        static vector<ll> val;
        idx.assign(size(C_) + 1, -1);
        val.assign(size(C_) + 1, INF * 2);

        auto f = [&](int i, int k, int a) {
            const int j = k - i;
            if (j < 0) return INF - j;
            if (j >= N) return INF + j;
            return a + B[j];
        };

        auto select_k = [&](int r, P A1, P A2) -> bool {
            auto [k, t] = C[r];
            auto [i1, a1] = A1;
            auto [i2, a2] = A2;
            if (k - i1 >= N) return 1;
            if (k - i2 < 0) return 0;
            return a1 + B[k - i1] > a2 + B[k - i2];
        };

        auto reduce = [&](int depth) {
            // O(M) 回の比較を行い、どの行においても最小値を取り得ない列を捨て、(列の個数) ≤ N とする
            const int dr = 1 << depth;
            const auto& A_prev = depth ? A_dfs[depth - 1] : A;
            auto& A_next = A_dfs[depth];
            A_next.clear();

            int r = 0;
            for (auto ia : A_prev) {
                while (r && select_k(r, A_next.back(), ia)) {
                    A_next.pop_back();
                    r -= dr;
                }
                if (r + dr <= size(C_)) {
                    A_next.push_back(ia);
                    r += dr;
                }
            }
        };
        auto interpolate = [&](int depth) {
            // 奇数行の最小値を M - 1 回の比較で求める
            const int dr = 1 << depth;
            auto& A = A_dfs[depth];
            // target_row = {dr, 3dr, 5dr, …}
            int r = dr;
            for (auto [i, a] : A)
                while (1) {
                    auto [k, t] = C[r];
                    if (chmin(val[r], f(i, k, a))) idx[r] = i;
                    if (r + dr * 2 > size(C_) || i < idx[r + dr]) break;
                    r += dr * 2;
                }
        };
        auto rec = [&](auto rec, int depth) {
            const int dr = 1 << depth;
            auto& A = A_dfs[depth];
            // row = {dr, 2dr, 3dr, …}
            reduce(depth);  // REDUCE step
            if (A.size() == 1) {
                auto [i, a] = A[0];
                for (int r = dr; r <= size(C_); r += dr) {
                    auto [k, t] = C[r];
                    idx[r] = i;
                    val[r] = f(i, k, a);
                }
                return;
            }
            rec(rec, depth + 1);        // 偶数行に対して SMAWK algorithm を適用
            return interpolate(depth);  // 奇数行の最小値を求める
        };

        rec(rec, 0);

        for (int r = 0; r <= size(C_); r++) {
            auto [k, t] = C[r];
            chmin(ans[t], val[r]);
        }
    };

    for (ll i = 1; i < Q * 2; i++) {
        solve(A_seg[i], C_seg[i]);
    }

    for (ll x : ans) cout << x << '\n';
}
0