結果
問題 | No.2988 Min-Plus Convolution Query |
ユーザー | 2qbingxuan |
提出日時 | 2024-12-22 03:42:47 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,640 KB |
testcase_01 | AC | 2 ms
13,640 KB |
testcase_02 | TLE | - |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | AC | 32 ms
15,140 KB |
testcase_06 | AC | 2 ms
13,764 KB |
testcase_07 | AC | 2 ms
13,760 KB |
testcase_08 | AC | 2 ms
13,764 KB |
testcase_09 | AC | 37 ms
13,764 KB |
testcase_10 | AC | 47 ms
21,032 KB |
testcase_11 | AC | 7 ms
13,764 KB |
testcase_12 | AC | 11 ms
21,032 KB |
testcase_13 | AC | 173 ms
13,760 KB |
testcase_14 | AC | 13 ms
13,768 KB |
testcase_15 | AC | 279 ms
13,772 KB |
testcase_16 | TLE | - |
testcase_17 | AC | 117 ms
13,768 KB |
testcase_18 | AC | 113 ms
13,764 KB |
testcase_19 | AC | 71 ms
13,764 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 | 3 ms
5,248 KB |
testcase_34 | AC | 3 ms
5,248 KB |
testcase_35 | AC | 3 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 3 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 3 ms
5,248 KB |
testcase_41 | AC | 2 ms
10,624 KB |
ソースコード
#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(); }