結果
問題 | No.2988 Min-Plus Convolution Query |
ユーザー |
![]() |
提出日時 | 2024-11-27 02:46:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 653 ms / 2,000 ms |
コード長 | 3,182 bytes |
コンパイル時間 | 1,718 ms |
コンパイル使用メモリ | 129,808 KB |
実行使用メモリ | 270,096 KB |
最終ジャッジ日時 | 2024-12-12 23:30:44 |
合計ジャッジ時間 | 17,705 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
// 時間軸をセグ木状に分割統治 + monotone minima#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) {auto minima = [&](auto minima, ll x1, ll x2, ll y1, ll y2) {if (x1 > x2) return;const ll x3 = (x1 + x2) / 2;auto [k, t] = C[x3];ll y3 = -1, mn = INF * 2;for (ll y = y1; y <= y2; y++) {auto [i, a] = A[y];const ll j = k - i;if (chmin(mn, [&] {if (j < 0) return INF - j;if (j >= N) return INF + j;return a + B[j];}())) y3 = y;}assert(y3 != -1);chmin(ans[t], mn);minima(minima, x1, x3 - 1, y1, y3);minima(minima, x3 + 1, x2, y3, y2);};if (A.empty() || C.empty()) return;minima(minima, 0, size(C) - 1, 0, size(A) - 1);};for (ll i = 1; i < Q * 2; i++) {solve(A_seg[i], C_seg[i]);}for (ll x : ans) cout << x << '\n';}