結果

問題 No.2988 Min-Plus Convolution Query
ユーザー 👑 tatyam
提出日時 2024-11-27 02:46:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 653 ms / 2,000 ms
コード長 3,182 bytes
コンパイル時間 1,718 ms
コンパイル使用メモリ 129,808 KB
実行使用メモリ 270,096 KB
最終ジャッジ日時 2024-12-12 23:30:44
合計ジャッジ時間 17,705 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 時間軸をセグ木状に分割統治 + monotone minima
#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) {
        auto minima = [&](auto minima, ll x1, ll x2, ll y1, ll y2) {
            if (x1 > x2) return;
            const ll x3 = (x1 + x2) / 2;
            auto [k, t] = C[x3];
            ll y3 = -1, mn = INF * 2;
            for (ll y = y1; y <= y2; y++) {
                auto [i, a] = A[y];
                const ll j = k - i;
                if (chmin(mn, [&] {
                        if (j < 0) return INF - j;
                        if (j >= N) 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);
    };

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

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