結果
問題 | No.1234 典型RMQ |
ユーザー |
|
提出日時 | 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 |
ソースコード
#ifndef LOCAL#include <bits/stdc++.h>using namespace std;#define debug(...) (void(0))#else#include "algo/debug.h"#endifvoid 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();}}