結果

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

ソースコード

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

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