結果
問題 | No.2988 Min-Plus Convolution Query |
ユーザー |
![]() |
提出日時 | 2024-11-27 02:45:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 678 ms / 2,000 ms |
コード長 | 5,204 bytes |
コンパイル時間 | 2,954 ms |
コンパイル使用メモリ | 144,552 KB |
実行使用メモリ | 275,596 KB |
最終ジャッジ日時 | 2024-12-12 23:30:33 |
合計ジャッジ時間 | 25,893 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
// 時間軸をセグ木状に分割統治 + SMAWK algorithm#include <algorithm>#include <array>#include <cassert>#include <climits>#include <cstdlib>#include <iostream>#include <vector>using namespace std;using ll = long long;const ll INF = LLONG_MAX / 4;using P = pair<int, int>;bool chmin(ll& a, ll b) { return a > b ? a = b, 1 : 0; }char* buf;ll buf_ind;template<class T> struct small {typedef T value_type;small() {}template<class U> small(const U&) {}T* allocate(size_t n) {if (n & 7) {n &= -8;n += 8;}buf_ind -= n * sizeof(T);buf_ind &= 0 - alignof(T);assert(buf_ind >= 0);return (T*)(buf + buf_ind);}void deallocate(T*, size_t) {}};using V = vector<P, small<P>>;int main() {buf_ind = 3 << 28;buf = (char*)malloc(buf_ind);cin.tie(0)->sync_with_stdio(0);ll N, Q;cin >> N >> Q;vector<ll> A(N), B(N);for (ll& x : A) cin >> x;for (ll& x : B) cin >> x;vector<array<ll, 3>> queries(Q);for (auto& [p, x, k] : queries) {cin >> p >> x >> k;p--;k -= 2;}// {L, R, i, a}vector<array<ll, 4>> A_range;{vector<ll> L(N);for (ll t = 0; t < Q; t++) {auto [p, x, k] = queries[t];A_range.push_back({L[p], t, p, A[p]});L[p] = t;A[p] = x;}for (ll i = 0; i < N; i++) A_range.push_back({L[i], Q, i, A[i]});}ranges::sort(A_range, {}, [](auto& x) { return x[2]; });vector<P> k_query; // {k, t}for (ll t = 0; t < Q; t++) {auto [p, x, k] = queries[t];k_query.push_back({k, t});}ranges::sort(k_query);vector<V> A_seg(Q * 2), C_seg(Q * 2);for (auto [L, R, i, a] : A_range) {L += Q;R += Q;for (; L < R; L >>= 1, R >>= 1) {if (L & 1) A_seg[L++].push_back({i, a});if (R & 1) A_seg[--R].push_back({i, a});}}for (auto [k, t] : k_query) {ll i = t + Q;do C_seg[i].push_back({k, t});while (i >>= 1);}vector<ll> ans(Q, INF);auto solve = [&](const V& A, const V& C_) {if (A.empty() || C_.empty()) return;auto C = begin(C_) - 1;static V A_dfs[20];static vector<int> idx;static vector<ll> val;idx.assign(size(C_) + 1, -1);val.assign(size(C_) + 1, INF * 2);auto f = [&](int i, int k, int a) {const int j = k - i;if (j < 0) return INF - j;if (j >= N) return INF + j;return a + B[j];};auto select_k = [&](int r, P A1, P A2) -> bool {auto [k, t] = C[r];auto [i1, a1] = A1;auto [i2, a2] = A2;if (k - i1 >= N) return 1;if (k - i2 < 0) return 0;return a1 + B[k - i1] > a2 + B[k - i2];};auto reduce = [&](int depth) {// O(M) 回の比較を行い、どの行においても最小値を取り得ない列を捨て、(列の個数) ≤ N とするconst int dr = 1 << depth;const auto& A_prev = depth ? A_dfs[depth - 1] : A;auto& A_next = A_dfs[depth];A_next.clear();int r = 0;for (auto ia : A_prev) {while (r && select_k(r, A_next.back(), ia)) {A_next.pop_back();r -= dr;}if (r + dr <= size(C_)) {A_next.push_back(ia);r += dr;}}};auto interpolate = [&](int depth) {// 奇数行の最小値を M - 1 回の比較で求めるconst int dr = 1 << depth;auto& A = A_dfs[depth];// target_row = {dr, 3dr, 5dr, …}int r = dr;for (auto [i, a] : A)while (1) {auto [k, t] = C[r];if (chmin(val[r], f(i, k, a))) idx[r] = i;if (r + dr * 2 > size(C_) || i < idx[r + dr]) break;r += dr * 2;}};auto rec = [&](auto rec, int depth) {const int dr = 1 << depth;auto& A = A_dfs[depth];// row = {dr, 2dr, 3dr, …}reduce(depth); // REDUCE stepif (A.size() == 1) {auto [i, a] = A[0];for (int r = dr; r <= size(C_); r += dr) {auto [k, t] = C[r];idx[r] = i;val[r] = f(i, k, a);}return;}rec(rec, depth + 1); // 偶数行に対して SMAWK algorithm を適用return interpolate(depth); // 奇数行の最小値を求める};rec(rec, 0);for (int r = 0; r <= size(C_); r++) {auto [k, t] = C[r];chmin(ans[t], val[r]);}};for (ll i = 1; i < Q * 2; i++) {solve(A_seg[i], C_seg[i]);}for (ll x : ans) cout << x << '\n';}