結果
問題 | No.875 Range Mindex Query |
ユーザー | stg1048599 |
提出日時 | 2019-09-07 00:17:57 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,643 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 162,580 KB |
実行使用メモリ | 22,136 KB |
最終ジャッジ日時 | 2024-06-24 22:42:21 |
合計ジャッジ時間 | 5,541 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
20,736 KB |
testcase_01 | AC | 9 ms
15,044 KB |
testcase_02 | AC | 9 ms
15,160 KB |
testcase_03 | AC | 8 ms
15,048 KB |
testcase_04 | AC | 9 ms
15,220 KB |
testcase_05 | AC | 8 ms
15,104 KB |
testcase_06 | AC | 8 ms
15,088 KB |
testcase_07 | AC | 9 ms
15,016 KB |
testcase_08 | AC | 8 ms
15,204 KB |
testcase_09 | AC | 9 ms
15,104 KB |
testcase_10 | AC | 10 ms
15,132 KB |
testcase_11 | TLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:32:27: warning: ‘index’ may be used uninitialized in this function [-Wmaybe-uninitialized] 32 | cout << index+1 << endl; | ^
ソースコード
#include <bits/stdc++.h> using namespace std; void init(vector<int>& d, vector<int>& a, int n); void update(vector<int>& d, int i, int x); int min_query(vector<int>& d, int l, int r, int k, int seg_l, int seg_r); int main(void){ const int MAX_N = 1e6; int n, q; cin >> n >> q; vector<int> a(MAX_N, INT_MAX); vector<int>dat(2*MAX_N-1, INT_MAX); for(int i = 0; i < n; i++) cin >> a[i]; n = pow(2, ceil(log2(n))); init(dat, a, n); for(int i = 0; i < q; i++){ int q_type, l, r; cin >> q_type >> l >> r; if(q_type == 1){ int lindex = l-1+n-1; int rindex = r-1+n-1; update(dat, lindex, a[r-1]); update(dat, rindex, a[l-1]); swap(a[l-1], a[r-1]); }else{ int min = min_query(dat, l-1, r, 0, 0, n); int index; for(int i = 0; a[i] < INT_MAX; i++){ if(a[i] == min) index = i; } cout << index+1 << endl; } } return 0; } void init(vector<int>& d, vector<int>& a, int n){ for(int i = 0; i < n; i++){ update(d, i+n-1, a[i]); } } void update(vector<int>& d, int i, int x){ d[i] = x; if(i > 0){ i = (i-1)/2; x = min(d[2*i+1], d[2*i+2]); update(d, i, x); }else{ return; } } int min_query(vector<int>& d, int l, int r, int k, int seg_l, int seg_r){ if(r <= seg_l || seg_r <= l) return INT_MAX; else if(l <= seg_l && seg_r <= r) return d[k]; else return min(min_query(d, l, r, 2*k+1, seg_l, (seg_l+seg_r)/2), min_query(d, l, r, 2*k+2, (seg_l+seg_r)/2, seg_r)); }