結果
問題 | No.2988 Min-Plus Convolution Query |
ユーザー | 2qbingxuan |
提出日時 | 2024-12-25 00:33:29 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 KB |
testcase_01 | AC | 2 ms
22,104 KB |
testcase_02 | TLE | - |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | AC | 31 ms
14,628 KB |
testcase_06 | AC | 1 ms
22,100 KB |
testcase_07 | AC | 2 ms
13,776 KB |
testcase_08 | AC | 2 ms
10,624 KB |
testcase_09 | AC | 37 ms
10,624 KB |
testcase_10 | AC | 46 ms
22,664 KB |
testcase_11 | AC | 6 ms
10,624 KB |
testcase_12 | AC | 9 ms
21,972 KB |
testcase_13 | AC | 125 ms
10,624 KB |
testcase_14 | AC | 11 ms
22,100 KB |
testcase_15 | AC | 223 ms
10,624 KB |
testcase_16 | TLE | - |
testcase_17 | AC | 98 ms
10,624 KB |
testcase_18 | AC | 91 ms
22,096 KB |
testcase_19 | AC | 70 ms
10,624 KB |
testcase_20 | TLE | - |
testcase_21 | TLE | - |
testcase_22 | TLE | - |
testcase_23 | TLE | - |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 1 ms
5,248 KB |
testcase_34 | AC | 2 ms
5,248 KB |
testcase_35 | AC | 1 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 1 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 2 ms
5,248 KB |
testcase_41 | AC | 1 ms
13,768 KB |
ソースコード
#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(); }