結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー kidodesu
提出日時 2026-01-10 15:56:36
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 3,481 ms / 5,000 ms
コード長 1,704 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,512 ms
コンパイル使用メモリ 348,160 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 13:15:54
合計ジャッジ時間 32,198 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main() {
    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<pair<int, int>> A;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        A.push_back({a, i});
    }

    vector<vector<int>> Q(q);
    int q1 = 0, q2 = 0;
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) {
            int p, v; cin >> p >> v;
            Q[i] = {1, p - 1, v};
            A.push_back({v, p - 1});
            q1++;
        } else {
            int r; cin >> r;
            Q[i] = {2, r};
            q2++;
        }
    }

    int total = n + q1;
    vector<int> B(total);
    iota(B.begin(), B.end(), 0);
    sort(B.begin(), B.end(), [&](int i, int j) { return A[i].first < A[j].first; });

    vector<int> Q2_pos(q2), Ts(total, 0), Te(total, q2), A_i(n);
    iota(A_i.begin(), A_i.end(), 0);

    int q1_c = 0, q2_c = 0;
    for (int i = 0; i < q; i++) {
        if (Q[i][0] == 1) {
            int pos = Q[i][1];
            Te[A_i[pos]] = q2_c;
            A_i[pos] = n + q1_c;
            Ts[A_i[pos]] = q2_c;
            q1_c++;
        } else {
            Q2_pos[q2_c] = Q[i][1];
            q2_c++;
        }
    }

    const int INF = 1 << 30;
    vector<int> Q2_p(q2, INF), Ans(q2, INF);

    for (int bi = 0; bi < total; bi++) {
        int i = B[bi];
        int val = A[i].first;
        int pos = A[i].second;
        for (int qi = Ts[i]; qi < Te[i]; qi++) {
            if (pos < Q2_pos[qi]) {
                Ans[qi] = min(Ans[qi], val ^ Q2_p[qi]);
                Q2_p[qi] = val;
            }
        }
    }
    
    for (int i = 0; i < q2; i++) {
        cout << Ans[i] << endl;
    }
    return 0;
}
0