結果
問題 | No.875 Range Mindex Query |
ユーザー | sigmani |
提出日時 | 2022-03-24 20:21:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 249 ms / 2,000 ms |
コード長 | 1,946 bytes |
コンパイル時間 | 971 ms |
コンパイル使用メモリ | 100,520 KB |
実行使用メモリ | 6,144 KB |
最終ジャッジ日時 | 2024-10-13 04:02:06 |
合計ジャッジ時間 | 3,675 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 3 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 192 ms
5,888 KB |
testcase_12 | AC | 159 ms
5,248 KB |
testcase_13 | AC | 140 ms
6,016 KB |
testcase_14 | AC | 131 ms
6,144 KB |
testcase_15 | AC | 178 ms
6,016 KB |
testcase_16 | AC | 232 ms
6,016 KB |
testcase_17 | AC | 249 ms
6,016 KB |
testcase_18 | AC | 243 ms
6,144 KB |
ソースコード
#include<iostream> #include<algorithm> #include<string> #include<math.h> #include <queue> #include<bitset> #include <iomanip> #include <map> #include <set> #include <stack> #include <climits> #define Inf 100000000 using namespace std; template <typename T> struct segtree { //元データx[i]はv[n+i] //v[i]の親はv[i/2],子はv[i*2]とv[i*2+1] vector<T> v; int n; const T init_value = make_pair(Inf, 0); segtree(vector<T>& x) { n = 1; while (true) { if (n >= x.size())break; n *= 2; } v.resize(2 * n, init_value); for (int i = 0; i < x.size(); i++) { v[n + i] = x[i]; } for (int i = n - 1; i >= 0; i--) { v[i] = func(v[i * 2], v[i * 2 + 1]); } } void update(int x, T val) { x += n; v[x] = val; while (true) { x = (x) / 2; v[x] = func(v[x * 2], v[x * 2 + 1]); if (x <= 0)break; } } //区間[l,r)におけるクエリ処理 T query(int l, int r) { T res = init_value; l += n; r += n; while (true) { if (l % 2 == 1) { res = func(v[l], res); l++; } if (r % 2 == 1) { res = func(v[r - 1], res); r--; } if (l >= r)break; l /= 2; r /= 2; } return res; } T func(T a, T b) { return min(a, b); } void show() { int n = 1; for (int i = 1; i < v.size(); i++) { for (int j = 0; j < n; j++) { if (j != 0)cout << ' '; cout << v[i + j]; } cout << endl; i += n - 1; n *= 2; } } }; int main() { int N, Q; cin >> N >> Q; vector<pair<int, int>> A(N); for (int i = 0; i < N; i++) { cin >> A[i].first; A[i].second = i+1; } segtree<pair<int, int>> seg(A); for (int i = 1; i <= Q; i++) { int T, L, R; cin >> T >> L >> R; L--; R--; if (T == 1) { int A = seg.query(L, L + 1).first; int B = seg.query(R, R + 1).first; seg.update(L, make_pair(B, L + 1)); seg.update(R, make_pair(A, R + 1)); } if (T == 2) { cout << seg.query(L, R + 1).second << endl; } } }