結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー otamay6
提出日時 2019-09-06 22:56:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,434 bytes
コンパイル時間 1,900 ms
コンパイル使用メモリ 172,052 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-24 20:36:28
合計ジャッジ時間 4,743 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;

int main(){
    int N,q;cin>>N>>q;
    int sn=sqrt(N);
    vector<int> a(N);
    vector<pair<int,int>> bukket(N,make_pair(1e9,-1));
    REP(i, N){
        cin >> a[i];
        if(bukket[i/sn].first>a[i]) bukket[i/sn]=make_pair(a[i],i);
    }
    REP(i,q){
        int query,l,r;
        cin>>query>>l>>r;
        l--;r--;
        if(query==1){
            swap(a[l],a[r]);
            int lx=l/sn,rx=r/sn;
            bukket[lx].first=1e9;bukket[rx].first=1e9;
            for(int j=lx*sn;j<(lx+1)*sn;++j){
                if(bukket[lx].first>a[j]) bukket[lx]=make_pair(a[j],j);
            }
            for(int j=rx*sn;j<(rx+1)*sn;++j){
                if(bukket[rx].first>a[j]) bukket[rx]=make_pair(a[j],j);
            }
        }
        if(query==2){
            pair<int,int> ans=make_pair(1e9,-1);
            int lx=l/sn+1,rx=r/sn-1;
            for(int j=lx;j<=rx;++j){
                if(bukket[j].first<ans.first) ans=bukket[j];
            }
            for(int j=l;j<=lx*sn;++j){
                if(a[j]<ans.first) ans=make_pair(a[j],j);
            }
            
            for(int j=r;j>=rx*sn;--j){
                if(a[j]<ans.first) ans=make_pair(a[j],j);
            }
            cout<<ans.second+1<<endl;
        }
    }
}
0