結果

問題 No.2988 Min-Plus Convolution Query
コンテスト
ユーザー 2qbingxuan
提出日時 2024-12-25 00:12:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,219 bytes
コンパイル時間 3,041 ms
コンパイル使用メモリ 266,520 KB
実行使用メモリ 26,240 KB
最終ジャッジ日時 2024-12-25 00:13:59
合計ジャッジ時間 61,294 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

// https://judge.yosupo.jp/submission/247405
constexpr int msb(unsigned int n){return n==0?-1:31-__builtin_clz(n);}
constexpr int msb(int n){return n==0?-1:31-__builtin_clz(n);}
constexpr int msb(unsigned long long n){return n==0?-1:63-__builtin_clzll(n);}
constexpr int msb(long long n){return n==0?-1:63-__builtin_clzll(n);}

template<typename Func>
std::vector<int>monotone_minima(int n,int m,const Func&f){
  std::vector<int>res(n);
  std::vector<tuple<int,int,int,int>>st(msb(n)*2+5);
  int p=0;
  st[p++]=std::make_tuple(0,n,0,m);
  while(p>0){
    auto [lx,rx,ly,ry]=st[--p];
    if(lx==rx)continue;
    if(lx+1==rx){
      res[lx]=ly;
      for(int i=ly+1;i<ry;i++)if(f(lx,res[lx],i))res[lx]=i;
    }
    else{
      int mid=(lx+rx)>>1;
      res[mid]=ly;
      for(int i=ly+1;i<ry;i++)if(f(mid,res[mid],i))res[mid]=i;
      st[p++]=std::make_tuple(lx,mid,ly,res[mid]+1);
      st[p++]=std::make_tuple(mid+1,rx,res[mid],ry);
    }
  }
  return res;
}
template<typename T,bool MIN=true>
std::vector<T>min_plus_convolution(const std::vector<T>&a,const std::vector<T>&b){
  int n=a.size(),m=b.size();
  auto f=[&](int i,int j,int k)->bool {
    if(i<k)return false;
    if(i-j>=n)return true;
    if constexpr(MIN)return a[i-j]+b[j]>a[i-k]+b[k];
    else return a[i-j]+b[j]<a[i-k]+b[k];
  };
  std::vector<int>argmin=monotone_minima(n+m-1,m,f);
  std::vector<T>res(n+m-1);
  for(int i=0;i<n+m-1;i++)res[i]=a[i-argmin[i]]+b[argmin[i]];
  return res;
}

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 = 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