結果

問題 No.875 Range Mindex Query
ユーザー nejinejinejineji
提出日時 2019-10-25 19:49:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 289 ms / 2,000 ms
コード長 2,406 bytes
コンパイル時間 1,610 ms
コンパイル使用メモリ 174,120 KB
実行使用メモリ 8,168 KB
最終ジャッジ日時 2023-09-29 00:37:04
合計ジャッジ時間 5,578 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 210 ms
7,900 KB
testcase_12 AC 173 ms
5,664 KB
testcase_13 AC 150 ms
7,592 KB
testcase_14 AC 147 ms
7,584 KB
testcase_15 AC 200 ms
7,844 KB
testcase_16 AC 266 ms
8,124 KB
testcase_17 AC 289 ms
8,120 KB
testcase_18 AC 278 ms
8,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) ((long long 1) << t)
#define PER(i,y,x) for(ll i=y; i>=x; i--)
#define SIZE(v) ll(v.size())
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
typedef long long ll;

struct segtree {
       vector<pll> tree;

       pll op(pll x, pll y) {
               return min(x, y);
       }
       pll const INIT_VALUE = {0, 0};
       ll n_ = 1;

       segtree(ll n) {
               while (n_ <= n) {
                       n_ *= 2;
               }
               tree = vector<pll>(n_ * 2 + 1, INIT_VALUE);
       }

       //k番目をxでupdate
       void update(ll k, ll x) {
               k += n_;
               tree[k] = {x, k-n_};
               while (k >= 1) {
                       k /= 2;
                       tree[k] = op(tree[k * 2], tree[k * 2 + 1]);
               }
       }

       pll val_o(ll a, ll b, ll k, ll l, ll r) {
               if (a <= l && r <= b) {
                       return tree[k];
               }
               else if (r <= a || b <= l) {
                       return {1e18, 0};
               }
               else {
                       pll x1 = val_o(a, b, k * 2, l, (l + r) / 2);
                       pll x2 = val_o(a, b, k * 2 + 1, (l + r) / 2, r);
                       return op(x1, x2);
               }

       }

       //[a,b)のvalueを求める
       pll val(ll a, ll b) {
               return val_o(a, b, 1, 0, n_);
       }

       ll val(ll a){
               return tree[a + n_].first;
       }
};

int main(){
        ll n, q;
        cin >> n >> q;
        segtree tree(n+1);
        REP(i,1,n){
                ll x;
                cin >> x;
                tree.update(i, x);
        }
        vll ans;
        REP(iii,1,q){
                ll c, l, r;
                cin >> c >> l >> r;
                if(c == 1){
                        ll x = tree.val(l);
                        ll y = tree.val(r);
                        tree.update(l, y);
                        tree.update(r, x);
                }
                else{
                        ans.push_back(tree.val(l, r+1).second);
                }
        }
        REP(i,0,ans.size() - 1){
                cout << ans[i];
                cout << endl;
        }
        
}
0