結果

問題 No.875 Range Mindex Query
ユーザー stg1048599stg1048599
提出日時 2019-09-07 00:17:57
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,643 bytes
コンパイル時間 2,983 ms
コンパイル使用メモリ 147,284 KB
実行使用メモリ 19,840 KB
最終ジャッジ日時 2023-09-07 04:06:08
合計ジャッジ時間 17,000 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
19,716 KB
testcase_01 AC 9 ms
14,644 KB
testcase_02 AC 9 ms
14,860 KB
testcase_03 AC 7 ms
15,344 KB
testcase_04 AC 8 ms
14,636 KB
testcase_05 AC 7 ms
14,600 KB
testcase_06 AC 9 ms
14,680 KB
testcase_07 AC 8 ms
14,728 KB
testcase_08 AC 8 ms
14,600 KB
testcase_09 AC 8 ms
14,604 KB
testcase_10 AC 9 ms
15,332 KB
testcase_11 TLE -
testcase_12 AC 1,471 ms
15,336 KB
testcase_13 AC 1,717 ms
14,800 KB
testcase_14 AC 1,621 ms
14,656 KB
testcase_15 TLE -
testcase_16 TLE -
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]
             cout << index+1 << endl;
                           ^

ソースコード

diff # 

#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));
}
0