結果
問題 |
No.1234 典型RMQ
|
ユーザー |
|
提出日時 | 2024-12-10 17:41:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 2,536 bytes |
コンパイル時間 | 3,470 ms |
コンパイル使用メモリ | 252,536 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-10 17:41:49 |
合計ジャッジ時間 | 8,902 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#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 = 400; 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(); } }