結果

問題 No.2988 Min-Plus Convolution Query
ユーザー tatyamtatyam
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// + 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 step
if (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';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0