#378102 (C++14) No.875 Range Mindex Query

• 問題: No.875 Range Mindex Query
• ユーザー: akun0716
• 提出日時: 2019-09-11 13:44:34
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 2,121 bytes
• コンパイル時間: 886 ms
• コンパイル使用メモリ: 85,988 KB
• 実行使用メモリ: 6,912 KB
• 最終ジャッジ日時: 2024-07-02 16:45:18
• 合計ジャッジ時間: 3,003 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 1
other	WA * 18

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 2147483647
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;
vector<int> value;
int N;
void update(int i, int x) {
    i += N - 1;
    value[i] = x;
    while (i > 0) {
        i = (i - 1) / 2;
        value[i] = min(value[i * 2 + 1], value[i * 2 + 2]);
    }
}
int query(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l)return LLINF;
    if (a <= l && r <= b)return value[k];
    else {
        int c1 = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int c2 = query(a, b, 2 * k + 2, (l + r) / 2,r);
        return min(c1, c2);
    }
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    N = 1;
    while (N < n)N *= 2;
    value = vector<int>(2 * N - 1);
    VI A(n);
    VI cnt(n + 1);
    REP(i, value.size())value[i] = LLINF;
    REP(i, n) {
        cin >> A[i];
        update(i, A[i]);
        cnt[A[i]] = i;
    }
    REP(i, q) {
        int c;
        cin >> c;
        c--;
        //REP(i, value.size())cout << value[i]<<" ";
        //cout << endl;
        if (!c) {
            int s,t;
            cin >> s >> t;
            swap(cnt[A[s - 1]], cnt[A[t - 1]]);
            update(s, A[t - 1]);
            update(t, A[s - 1]);
        //  REP(i, value.size())cout << value[i] << " ";
        }
        else {
            int s, t;
            cin >> s >> t;
            cout << cnt[query(s, t + 1, 0, 0, N)]+1 << endl;
        }
    }
    
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX