結果

問題 No.2988 Min-Plus Convolution Query
ユーザー 👑 tatyam
提出日時 2024-11-27 02:46:23
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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