結果

問題 No.2988 Min-Plus Convolution Query
コンテスト
ユーザー 2qbingxuan
提出日時 2024-12-22 03:42:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,347 bytes
コンパイル時間 3,555 ms
コンパイル使用メモリ 262,828 KB
実行使用メモリ 27,892 KB
最終ジャッジ日時 2024-12-22 03:43:48
合計ジャッジ時間 61,650 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

// a is convex a[i+1]-a[i] <= a[i+2]-a[i+1]
vector<lld> min_plus_convolution(auto &a, auto &b) {
  const int n = (int)a.size(), m = (int)b.size();
  vector<lld> c(n + m - 1, numeric_limits<lld>::max());
  auto dc = [&](auto Y, int l, int r, int jl, int jr) {
    if (l > r) return;
    int mid = (l + r) / 2, from = -1;
    lld &best = c[mid];
    for (int j = jl; j <= jr; j++)
      if (int i = mid - j; i >= 0 && i < n)
        if (best > a[i]+b[j]) best = a[i]+b[j], from = j;
    Y(Y, l, mid-1, jl, from); Y(Y, mid+1, r, from, jr);
  };
  return dc(dc, 0, n-1+m-1, 0, m-1), c;
}

int 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 = min_plus_convolution(B, masked);

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

    for (const auto &[p, x, k] : qs) {
      A[p] = x;
      lld ans = c[k];
      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