結果

問題 No.875 Range Mindex Query
ユーザー stg1048599
提出日時 2019-09-07 00:17:57
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
      |                           ^

ソースコード

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