結果
問題 | No.1234 典型RMQ |
ユーザー | Example0911 |
提出日時 | 2020-09-18 22:38:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 282 ms / 2,000 ms |
コード長 | 4,153 bytes |
コンパイル時間 | 1,684 ms |
コンパイル使用メモリ | 169,788 KB |
実行使用メモリ | 10,404 KB |
最終ジャッジ日時 | 2023-08-08 18:49:05 |
合計ジャッジ時間 | 8,805 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 268 ms
8,140 KB |
testcase_07 | AC | 226 ms
4,376 KB |
testcase_08 | AC | 282 ms
9,840 KB |
testcase_09 | AC | 252 ms
6,464 KB |
testcase_10 | AC | 275 ms
9,148 KB |
testcase_11 | AC | 262 ms
7,780 KB |
testcase_12 | AC | 249 ms
5,908 KB |
testcase_13 | AC | 230 ms
4,376 KB |
testcase_14 | AC | 251 ms
6,128 KB |
testcase_15 | AC | 247 ms
5,420 KB |
testcase_16 | AC | 276 ms
8,788 KB |
testcase_17 | AC | 254 ms
6,504 KB |
testcase_18 | AC | 219 ms
4,380 KB |
testcase_19 | AC | 279 ms
9,872 KB |
testcase_20 | AC | 209 ms
10,112 KB |
testcase_21 | AC | 270 ms
7,752 KB |
testcase_22 | AC | 236 ms
10,336 KB |
testcase_23 | AC | 233 ms
10,404 KB |
testcase_24 | AC | 232 ms
10,016 KB |
testcase_25 | AC | 231 ms
10,340 KB |
testcase_26 | AC | 233 ms
10,124 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,376 KB |
testcase_29 | AC | 1 ms
4,376 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long int N, Q; /* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体 set(i,x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n) add(a,b,x): 区間[a,b) の要素に x を加算。O(log(n)) query(a,b): 区間 [a,b) での最小の要素を取得。O(log(n)) find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n)) find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n)) */ template <typename T> struct RMQ { const T INF = numeric_limits<T>::max(); int n; vector<T> dat, lazy; RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, 0) { int x = 1; while (n_ > x) x *= 2; n = x; } void set(int i, T x) { dat[i + n - 1] = x; } void build() { for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]); } /* lazy eval */ void eval(int k) { if (lazy[k] == 0) return; // 更新するものが無ければ終了 if (k < n - 1) { // 葉でなければ子に伝搬 lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } // 自身を更新 dat[k] += lazy[k]; lazy[k] = 0; } void add(int a, int b, T x, int k, int l, int r) { eval(k); if (a <= l && r <= b) { // 完全に内側の時 lazy[k] += x; eval(k); } else if (a < r && l < b) { // 一部区間が被る時 add(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子 add(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子 dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } void add(int a, int b, T x) { add(a, b, x, 0, 0, n); } T query_sub(int a, int b, int k, int l, int r) { eval(k); if (r <= a || b <= l) { // 完全に外側の時 return INF; } else if (a <= l && r <= b) { // 完全に内側の時 return dat[k]; } else { // 一部区間が被る時 T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2); T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } } T query(int a, int b) { return query_sub(a, b, 0, 0, n); } T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); } // 存在しなければ a-1 T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); } // 存在しなければ b T find_rightest_sub(int a, int b, int x, int k, int l, int r) { eval(k); if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1 return a - 1; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); if (vr != a - 1) { // 右の部分木を見て a-1 以外ならreturn return vr; } else { // 左の部分木を見て値をreturn return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); } } } T find_leftest_sub(int a, int b, int x, int k, int l, int r) { eval(k); if (dat[k] > x || r <= a || b <= l) { // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b return b; } else if (k >= n - 1) { // 自分が葉ならその位置をreturn return (k - (n - 1)); } else { int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2); if (vl != b) { // 左の部分木を見て b 以外ならreturn return vl; } else { // 右の部分木を見て値をreturn return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r); } } } /* debug */ inline T operator[](int a) { return query(a, a + 1); } void print() { for (int i = 0; i < n; ++i) { cout << (*this)[i]; if (i != n) cout << ","; } cout << endl; } }; signed main() { cin >> N; vector<int>a(N); for (int i = 0; i < N; i++)cin >> a[i]; cin >> Q; RMQ<int> rmq(N); for (int i = 0; i < N; i++) { rmq.set(i, a[i]); } rmq.build(); for (int i = 0; i < Q; i++) { int c, x, y; cin >> c >> x >> y; x--; y--; int t; cin >> t; if (c == 1) rmq.add(x, y+1, t); else cout << rmq.query(x, y + 1) << endl; } return 0; }