結果

問題 No.2988 Min-Plus Convolution Query
コンテスト
ユーザー 2qbingxuan
提出日時 2024-12-25 00:33:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,267 bytes
コンパイル時間 3,713 ms
コンパイル使用メモリ 268,600 KB
実行使用メモリ 29,764 KB
最終ジャッジ日時 2024-12-25 00:34:34
合計ジャッジ時間 55,649 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define all(x) begin(x), end(x)
#ifdef local
#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

namespace nachia {

template<class Elem>
struct SmawkAlgorithm {

template<class Gen, class Cmp = std::less<Elem>>
std::vector<std::pair<Elem, int>> Solve(
    int height, int width,
    Gen gen,
    Cmp cmp = Cmp()
){
    if(height == 0) return std::vector<std::pair<Elem, int>>(0);
    auto reduce = [&](int yst, const std::vector<int>& cols)
     -> std::vector<int> {
        int w = int(cols.size());
        std::vector<int> idx;
        int r = -1;
        for(int q=0; q<w; q++){
            if(idx.empty()){
                idx.push_back(q);
                r += yst;
                continue;
            }
            int a = cols[idx.back()];
            int b = cols[q];
            if(cmp(gen(r,a), gen(r,b))){
                if(r+yst < height){ idx.push_back(q); r += yst; }
            } else {
                idx.pop_back(); q--; r -= yst;
            }
        }
        return idx;
    };
    auto ysts = std::vector<int>(1,1);
    auto cols = std::vector<std::vector<int>>(1);
    for(int i=0; i<width; i++) cols[0].push_back(i);
    cols[0] = reduce(1, cols[0]);
    while(true){
        int nxst = ysts.back() * 2;
        if(height < nxst) break;
        auto nxc = reduce(nxst, cols.back());
        int w = nxc.size();
        for(int i=0; i<w; i++) nxc[i] = cols.back()[nxc[i]];
        cols.push_back(move(nxc));
        ysts.push_back(nxst);
    }
    std::vector<std::pair<Elem, int>> ans(height, std::make_pair(gen(0,0), 0));
    while(cols.size()){
        auto x = std::move(cols.back()); cols.pop_back();
        int st = ysts.back(); ysts.pop_back();
        int p = 0;
        for(int y=st-1; y<height; y+=st*2){
            int r = y+st < height ? ans[y+st].second : width-1;
            ans[y] = std::make_pair(gen(y,x[p]), x[p]);
            while(p+1 < int(x.size()) && x[p+1] <= r){
                int xp = x[++p];
                auto fxp = gen(y,xp);
                if(!cmp(ans[y].first, fxp)) ans[y] = std::make_pair(fxp, xp);
            }
        }
    }
    return ans;
}

};
} // namespace nachia


namespace nachia {

template<class Elem>
std::vector<std::pair<Elem, int>> ConvexMinPlusConvolution(
    const std::vector<Elem>& a,
    const std::vector<Elem>& b,
    Elem Inf
){
    int n = a.size();
    int m = b.size();
    return nachia::SmawkAlgorithm<Elem>().Solve(
        n+m-1, m,
        [&](int y, int x) -> Elem {
            return (y < x || n <= y-x) ? Inf : a[y-x] + b[x]; } );
}
} // namespace nachia


signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N, Q;
  cin >> N >> Q;
  vector<lld> A(N + 1), B(N + 1);
  A[0] = B[0] = 4e9;
  for (int i = 1; i <= N; i++)
    cin >> A[i];
  for (int i = 1; i <= N; i++)
    cin >> B[i];

  vector<tuple<int, int, int>> qs;
  auto calc = [&] {
    vector<lld> masked = A;

    vector<int> ps;
    ps.reserve(qs.size());
    for (const auto &[p, x, k] : qs) {
      masked[p] = 4e9;
      ps.emplace_back(p);
    }
    auto c = nachia::ConvexMinPlusConvolution(B, masked, ((lld)8e9) + 1);

    sort(all(ps));
    ps.erase(unique(all(ps)), ps.end());

    for (const auto &[p, x, k] : qs) {
      A[p] = x;
      lld ans = c[k].first;
      debug(ans);
      orange(all(ps));
      for (int i : ps)
        if (k - i >= 1 && k - i <= N)
          ans = min(ans, A[i] + B[k - i]);
      cout << ans << '\n';
    }
  };

  constexpr int BS = 600;
  for (int i = 0; i < Q; i++) {
    int p, x, k;
    cin >> p >> x >> k;
    qs.emplace_back(p, x, k);

    if (qs.size() > BS) {
      calc();
      qs.clear();
    }
  }
  calc();
}
0