結果

問題 No.2988 Min-Plus Convolution Query
ユーザー tatyamtatyam
提出日時 2024-11-27 02:46:23
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 795 ms / 2,000 ms
コード長 3,520 bytes
コンパイル時間 2,427 ms
コンパイル使用メモリ 138,008 KB
実行使用メモリ 44,528 KB
最終ジャッジ日時 2024-12-12 23:30:30
合計ジャッジ時間 28,637 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 785 ms
44,272 KB
testcase_03 AC 773 ms
44,400 KB
testcase_04 AC 782 ms
44,400 KB
testcase_05 AC 87 ms
12,440 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 136 ms
15,688 KB
testcase_10 AC 47 ms
7,096 KB
testcase_11 AC 15 ms
5,248 KB
testcase_12 AC 31 ms
5,496 KB
testcase_13 AC 244 ms
16,728 KB
testcase_14 AC 40 ms
5,872 KB
testcase_15 AC 406 ms
25,412 KB
testcase_16 AC 705 ms
39,972 KB
testcase_17 AC 337 ms
25,252 KB
testcase_18 AC 353 ms
25,376 KB
testcase_19 AC 290 ms
25,248 KB
testcase_20 AC 795 ms
44,272 KB
testcase_21 AC 782 ms
44,400 KB
testcase_22 AC 786 ms
44,404 KB
testcase_23 AC 779 ms
44,400 KB
testcase_24 AC 788 ms
44,400 KB
testcase_25 AC 728 ms
44,524 KB
testcase_26 AC 726 ms
44,396 KB
testcase_27 AC 793 ms
44,404 KB
testcase_28 AC 787 ms
44,404 KB
testcase_29 AC 789 ms
44,400 KB
testcase_30 AC 788 ms
44,404 KB
testcase_31 AC 793 ms
44,528 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 2 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 3 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 2 ms
5,248 KB
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <array>
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
bool chmin(ll& a, ll b) { return a > b ? a = b, 1 : 0; }

struct A_type {
    int l, r, i, a;
};
struct C_type {
    int k, t;
};
void main2(const ll Q, vector<A_type> A, vector<ll> B, vector<C_type> C) {
    ranges::sort(A, {}, &A_type::i);
    ranges::sort(C, {}, &C_type::k);

    vector<A_type> A_dfs[20];
    vector<C_type> C_dfs[20];
    A_dfs[0] = move(A);
    C_dfs[0] = move(C);

    vector<ll> ans(Q, INF);
    auto update = [&](const vector<A_type>& A, const vector<C_type>& C) {
        auto minima = [&](auto minima, ll x1, ll x2, ll y1, ll y2) -> void {
            if (x1 > x2) return;
            const ll x3 = (x1 + x2) / 2;
            const auto [k, t] = C[x3];
            ll mn = INF * 2, y3 = -1;
            for (ll y = y1; y <= y2; y++) {
                const auto [l, r, i, a] = A[y];
                const ll j = k - i;
                if (chmin(mn, [&] {
                        if (j < 0) return INF - j;
                        if (j >= ssize(B)) return INF + j;
                        return a + B[j];
                    }())) y3 = y;
            }
            assert(y3 != -1);
            chmin(ans[t], mn);
            minima(minima, x1, x3 - 1, y1, y3);
            minima(minima, x3 + 1, x2, y3, y2);
        };
        if (A.empty() || C.empty()) return;
        minima(minima, 0, size(C) - 1, 0, size(A) - 1);
    };

    auto dfs = [&](auto dfs, int depth, int L, int R) -> void {
        auto& A = A_dfs[depth];
        auto& C = C_dfs[depth];
        if (A.empty() || C.empty()) return;
        // A から [L, R) subset [l, r) である要素を A_cover に移す
        static vector<A_type> A_cover;
        A_cover.clear();
        erase_if(A, [&](const A_type& a) {
            if (a.l > L || R > a.r) return 0;
            A_cover.push_back(a);
            return 1;
        });
        assert(ranges::is_sorted(A_cover, {}, &A_type::i));
        update(A_cover, C);

        if (R - L == 1) return;
        const int M = (L + R) / 2;
        auto& A2 = A_dfs[depth + 1];
        auto& C2 = C_dfs[depth + 1];
        A2.clear();
        C2.clear();
        ranges::copy_if(A, back_inserter(A2), [&](const A_type& a) { return a.l < M; });
        erase_if(C, [&](const C_type& c) {
            if (M <= c.t) return 0;
            C2.push_back(c);
            return 1;
        });
        dfs(dfs, depth + 1, L, M);
        A2.clear();
        ranges::copy_if(A, back_inserter(A2), [&](const A_type& a) { return M < a.r; });
        swap(C, C2);
        dfs(dfs, depth + 1, M, R);
    };
    dfs(dfs, 0, 0, Q);

    for (ll x : ans) cout << x << '\n';
}
int main() {
    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;
    }

    vector<A_type> A_range;
    vector<ll> L(N);
    for (ll t = 0; t < Q; t++) {
        auto [p, x, k] = queries[t];
        A_range.emplace_back(L[p], t, p, A[p]);
        L[p] = t;
        A[p] = x;
    }
    for (ll i = 0; i < N; i++) A_range.emplace_back(L[i], Q, i, A[i]);

    vector<C_type> C_query;
    for (ll t = 0; t < Q; t++) {
        auto [p, x, k] = queries[t];
        C_query.emplace_back(k, t);
    }

    main2(Q, A_range, B, C_query);
}
0