結果

問題 No.1234 典型RMQ
ユーザー ooaiuooaiu
提出日時 2024-12-10 18:01:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 234 ms / 2,000 ms
コード長 2,536 bytes
コンパイル時間 3,681 ms
コンパイル使用メモリ 252,300 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-10 18:01:50
合計ジャッジ時間 10,434 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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

#ifndef LOCAL
#include <bits/stdc++.h>
using namespace std;
#define debug(...) (void(0))
#else
#include "algo/debug.h"
#endif
void solve() {
using S = int64_t;
int N;
cin >> N;
constexpr int M = 512;
constexpr S inf = 1e18;
int sz = 1;
while (sz * M < N) sz++;
vector<vector<S>> dat(sz, vector<S>(M, inf));
{
int id = 0;
for (int i = 0; i < sz; i++) {
for (int j = 0; j < M; j++) {
if (id++ < N) {
S a;
cin >> a;
dat[i][j] = a;
}
}
}
}
int Q;
cin >> Q;
const auto Idx = [&](int x) -> pair<int, int> { return pair<int, int>{x / M, x % M}; };
vector<S> precalc(sz, inf);
const auto Calc = [&](int i) -> int64_t {
int64_t res = inf;
for (int j = 0; j < M; j++) res = min(res, dat[i][j]);
return precalc[i] = res;
};
for (int i = 0; i < sz; i++) Calc(i);
vector<S> off(sz);
const auto Add = [&](int l, int r, int x) -> void {
auto [li, lj] = Idx(l);
auto [ri, rj] = Idx(r);
if (li != ri) {
for (int i = lj; i < M; i++) dat[li][i] += x;
for (int i = 0; i <= rj; i++) dat[ri][i] += x;
for (int i = li + 1; i < ri; i++) off[i] += x;
Calc(li), Calc(ri);
} else {
for (int i = l; i <= r; i++) {
auto [ni, nj] = Idx(i);
dat[ni][nj] += x;
}
Calc(li);
}
};
const auto Prod = [&](int l, int r) -> S {
auto [li, lj] = Idx(l);
auto [ri, rj] = Idx(r);
int64_t res = inf;
if (li != ri) {
for (int i = lj; i < M; i++) res = min(res, dat[li][i] + off[li]);
for (int i = 0; i <= rj; i++) res = min(res, dat[ri][i] + off[ri]);
for (int i = li + 1; i < ri; i++) res = min(res, precalc[i] + off[i]);
} else {
for (int i = l; i <= r; i++) {
auto [ni, nj] = Idx(i);
res = min(res, dat[ni][nj] + off[ni]);
}
}
return res;
};
while (Q--) {
int k, l, r, x;
cin >> k >> l >> r >> x;
l--, r--;
if (k == 1) {
Add(l, r, x);
} else {
cout << Prod(l, r) << endl;
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1;
// std::cin >> tt;
while (tt--) {
solve();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0