結果

問題 No.2809 Sort Query
ユーザー Pres1dentPres1dent
提出日時 2024-07-14 21:27:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,185 bytes
コンパイル時間 7,366 ms
コンパイル使用メモリ 319,824 KB
実行使用メモリ 42,044 KB
最終ジャッジ日時 2024-07-14 21:28:39
合計ジャッジ時間 91,387 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1,106 ms
24,448 KB
testcase_02 AC 1,066 ms
24,448 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 1,089 ms
24,392 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 1,107 ms
24,448 KB
testcase_10 AC 1,085 ms
24,320 KB
testcase_11 AC 1,100 ms
41,892 KB
testcase_12 AC 1,014 ms
41,892 KB
testcase_13 AC 1,061 ms
42,000 KB
testcase_14 AC 1,083 ms
42,044 KB
testcase_15 AC 1,069 ms
42,032 KB
testcase_16 AC 1,081 ms
41,916 KB
testcase_17 AC 1,065 ms
41,896 KB
testcase_18 AC 1,047 ms
41,884 KB
testcase_19 AC 1,079 ms
41,892 KB
testcase_20 AC 1,090 ms
41,880 KB
testcase_21 AC 1,162 ms
42,028 KB
testcase_22 AC 1,174 ms
42,032 KB
testcase_23 AC 1,191 ms
41,932 KB
testcase_24 AC 1,185 ms
41,764 KB
testcase_25 AC 1,199 ms
41,892 KB
testcase_26 AC 1,318 ms
33,580 KB
testcase_27 AC 1,280 ms
33,584 KB
testcase_28 AC 1,260 ms
33,588 KB
testcase_29 AC 1,278 ms
33,596 KB
testcase_30 AC 1,287 ms
33,600 KB
testcase_31 AC 1,220 ms
33,468 KB
testcase_32 AC 1,208 ms
33,592 KB
testcase_33 AC 1,212 ms
33,620 KB
testcase_34 AC 1,220 ms
33,596 KB
testcase_35 AC 1,210 ms
33,592 KB
testcase_36 AC 1,047 ms
42,036 KB
testcase_37 AC 1,045 ms
41,892 KB
testcase_38 AC 1,060 ms
42,032 KB
testcase_39 AC 1,016 ms
42,040 KB
testcase_40 AC 1,019 ms
42,032 KB
testcase_41 AC 1,427 ms
19,712 KB
testcase_42 AC 1,415 ms
19,712 KB
testcase_43 AC 1,442 ms
19,712 KB
testcase_44 AC 1,544 ms
19,712 KB
testcase_45 AC 1,417 ms
19,712 KB
testcase_46 AC 1,112 ms
19,712 KB
testcase_47 AC 1,129 ms
19,584 KB
testcase_48 AC 1,109 ms
19,840 KB
testcase_49 AC 1,179 ms
19,712 KB
testcase_50 AC 1,116 ms
19,712 KB
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 AC 681 ms
18,816 KB
testcase_61 AC 899 ms
22,272 KB
testcase_62 AC 649 ms
14,080 KB
testcase_63 WA -
testcase_64 AC 1,102 ms
23,168 KB
testcase_65 AC 565 ms
16,256 KB
testcase_66 WA -
testcase_67 WA -
testcase_68 AC 2 ms
6,944 KB
testcase_69 WA -
testcase_70 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using lll = __int128;
using i64 = long long;
using i128 = __int128;
constexpr int INF = numeric_limits<int>::max();
constexpr ll LNF= numeric_limits<ll>::max();
using ull = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using l_l = pair<ll, ll>;
using d_d = pair<double, double>;
using s_s = pair<string, string>;
using i_i_i = tuple<int, int, int>;
using i_i_i_i = tuple<int, int, int, int>;
using i_i_i_i_i = tuple<int, int, int, int, int>;
using l_l_l = tuple<ll, ll, ll>;
using l_l_l_l = tuple<ll, ll, ll, ll>;
using l_l_l_l_l = tuple<ll, ll, ll, ll, ll>;
using _bool = int;
#define rep2(i, m, n) for (ll i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (ll i = (n)-1; i >= (m); --i)
#define drep(i, n) drep2(i, 0, n)
#define ifbit(n,k) ((n>>k)&1) //if kth bit of n is on then true (sitakara, 0-indexed)
#define zpad(i) cout << setfill('0') << setw(i)
#define dout cout << fixed << setprecision(10)
#define douts(i) cout << fixed << setprecision(i) << scientific
#define pcnt __builtin_popcountll
template <class T, class U> bool chmax(T &l, const U &r) { if (l < r) { l = r; return true; } return false; }
template <class T, class U> bool chmin(T &l, const U &r) { if (l > r) { l = r; return true; } return false; }
template <class T> pair<int, bool> ub(const vector<T> &v, const T &key) { int ind = upper_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rub(const vector<T> &v, const T &key) { int ind = upper_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
template <class T> pair<int, bool> lb(const vector<T> &v, const T &key) { int ind = lower_bound(v.begin(), v.end(), key) - v.begin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair(ind, true); }
template <class T> pair<int, bool> rlb(const vector<T> &v, const T &key) { int ind = lower_bound(v.rbegin(), v.rend(), key, [](const T & l, const T & r) { return l > r; }) - v.rbegin(); if (ind == (int)v.size()) return make_pair(0, false); return make_pair((int)v.size() - 1 - ind, true); }
vector<int> di = { -1, 0, 1, 0 };
vector<int> dj = { 0, 1, 0, -1 };
ll my_pow(ll a, int x) { assert(x >= 0); ll ret = 1; rep(i, x) { assert(LNF / x > a); ret *= a; } return ret; }

using ll = long long;
// .insert(value)
//   - split
//   - merge
// .exist(value)
// .erase(value)
// .dump
// .size()
// .at(index) i the element
// .upper_bound(value)
// .lower_bound(value)
// for (auto : treap)

template <class T> struct Treap {
private:
  struct Node {
    T key;
    int pri, sz;
    Node *l, *r;
    Node(T k, int p) : key(k), pri(p), l(nullptr), r(nullptr) {}
  } *root = nullptr;
  int size(Node *t) const {
    return (t ? t->sz : 0);
  }
  void update(Node *&t) {
    if (!t) return;
    t->sz = size(t->l) + size(t->r) + 1;
  }
  // l (key より小さい), r (keyより大きい)
  void split(Node *&t, T key, Node *&l, Node *&r) {
   // cerr << "split cur (t) " << (t ? t->key : -1) << endl;
    if (!t) {
//       cerr << "ぬるぽ" << endl;
      l = r = nullptr;
    } else if (key < t->key) {
//       cerr << "address (t, t->l) " << t << " " << t->l << endl;
      r = t;
//       cerr << "address (t->l, r->l) " << t->l << " " << r->l << endl;
      split(t->l, key, l, r->l);
    } else {
//     cerr << "split 1 (t) " << (t ? t->key : -1) << endl;
      l = t;
//       cerr << "address (t, l->r, r) " << t << " " << l->r << " " << r << endl;
      split(t->r, key, l->r, r);
//       cerr << "address (t, l->r, r) " << t << " " << l->r << " " << r << " ";
//       if (t) cerr << t->r;
      // else cerr << "ぬるぽ";
//       cerr << endl;
//     cerr << "split 2 (t) " << (t ? t->key : -1) << endl;
//     cerr << "split 3 (t) " << (t ? t->key : -1) << endl;
      // assert(false);
    }
//     cerr << "split end (t) " << (t ? t->key : -1) << endl;
//     cerr << "split end (l, r) " << (l ? l->key : -1) << " " << (r ? r->key : -1) << endl;
    update(l), update(r);
  }
  void insert(Node *&t, Node *v) {
    if (t == root) {
//       cerr << "insert " << v->key << endl;
    }
    if (!t) {
      t = v;
    } else if (v->pri < t->pri) {
      insert(v->key < t->key ? t->l : t->r, v);
    } else {
      split(t, v->key, v->l, v->r);
      t = v;
    }
    update(t);
  }
  void merge(Node *&t, Node *l, Node *r) {
    if (!l or !r) {
      t = (l ? l : r);
    } else if (l->pri < r->pri) {
      t = r;
      merge(t->l, l, r->l);
    } else {
      t = l;
      merge(t->r, l->r, r);
    }
    update(t);
  }
  void erase(Node *&t, T key) {
    if (!t) return;
    if (t->key == key) {
      merge(t, t->l, t->r);
    } else {
      erase(key < t->key ? t->l : t->r, key);
    }
    update(t);
  }
  bool exist(Node *&t, T key) const {
    if (!t) {
      return false;
    } else if (t->key == key) {
      return true;
    } else if (key < t->key) {
      return exist(t->l, key);
    } else {
      return exist(t->r, key);
    }
  }
  void all(Node *t, vector<T>& ret) const {
    if (!t) return;
    all(t->l, ret);
    ret.emplace_back(t->key);
    all(t->r, ret);
  }
  T split2(Node *t, int ind) {
    if (!t) assert(0 && "couln't find by index");
    int t_ind = size(t->l);
//     cerr << "split2 " << t->key << " " << ind << endl;
    if (ind == t_ind) {
      return t->key;
    } else if (ind < t_ind) {
      return split2(t->l, ind);
    } else {
      return split2(t->r, ind - t_ind - 1);
    }
    update(t);
  }

public:
  void insert(T key) {
    insert(root, new Node(key, rand()));
  }
  void erase(T key) {
    erase(root, key);
  }
  bool exist(T key) {
    return exist(root, key);
  }
  vector<T> all(void) {
    vector<T> ret;
    all(root, ret);
    return ret;
  }
  int size(void) {
    return size(root);
  }
  T at(int ind) {
    assert(0 <= ind and ind < size());
    return split2(root, ind);
  }
  void dump(void) {
    int d = 0;
    vector<vector<T>> debug;
    auto rec = [&](auto&& self, Node *v) -> void {
      if (d == debug.size()) debug.push_back({});
      if (!v) {
        debug[d].push_back(-1);
        return;
      }
      debug[d].push_back(v->key);
      d++;
      self(self, v->l);
      self(self, v->r);
      d--;
    };
    rec(rec, root);
    int sum = 0;
    for (auto v : debug) {
      int cnt = 0;
      int sz = 0;
      for (auto e : v) {
        if (e != -1) {
          sz += 1;
          sum++;
        }
      }
//       cerr << "size " << sz << " ";
      for (auto e : v) {
//         cerr << e << " ";
      }
//       cerr << endl;
    }
//     cerr << "sum " << sum << endl;
  }
};

int main() {
// void solve () {
  int n, q; cin >> n >> q;
  vector<ll> A(n); rep(i, n) { cin >> A[i]; }
  Treap<ll> t;
  int cnt = 0;
  rep(i, n) { t.insert(A[i]); }
  map<int, ll> mp;
  rep(i, q) {
    int op; cin >> op;
//     cerr << i << " " << op << endl;
    if (op == 1) {
      ll k, x; cin >> k >> x;
      k--;
      mp[k] = x;
    } else if (op == 2) {
      vector<ll> tmp;
      for (auto [k, v] : mp) {
//         cerr << "i, n, k, size " << i << " " << n << " " << k << " " << t.size() << endl;
        auto res = t.at(k);
//         cerr << "res " << res << " " << t.exist(res) << endl;
        tmp.push_back(t.at(k));
      }
      for (auto e : tmp) {
        assert(t.exist(e));
        t.erase(e);
//         cerr << "erase " << t.size() << endl;
        // t.dump();
      }
      for (auto [k, v] : mp) {
        t.insert(v);
//         cerr << "insert " << t.size() << endl;
        // t.dump();
      }
      mp = {};
//       cerr << t.size() << " " << n << endl;
      assert(t.size() == n);
    } else {
      int k; cin >> k;
      k--;
      if (mp.find(k) == mp.end()) {
//         cerr << "n, k, size " << i << " " << n << " " << k << " " << t.size() << endl;
        cout << t.at(k) << endl;
      } else {
        cout << mp[k] << endl;
      }
    }
  }
  
}
// int main() {
//   Treap<int> t;
//   t.insert(3);
//   t.insert(3);
//   t.insert(4);
//   t.insert(5);
//   t.insert(5);
//   t.insert(7);
//   t.insert(0);
//   int n = 10;
//   for (int i = 0; i < n; i++) {
//     cerr << t.exist(i) << " ";
//   }
//   cerr << endl;
//   for (auto e : t.all()) {
//     cerr << e << " ";
//   }
//   cerr << endl;
//   cerr << "size " << t.size() << endl;
//   t.erase(5);
//   t.erase(4);
//   for (int i = 0; i < n; i++) {
//     cerr << t.exist(i) << " ";
//   }
//   cerr << endl;
//   cerr << "size " << t.size() << endl;
//   cerr << "DUMP" << endl;
//   t.dump();
//   cerr << "DUMP" << endl;
//   for (auto e : t.all()) {
//     cerr << e << " ";
//   }
//   cerr << endl;
//   cerr << t.size() << endl;
//   cerr << "at test" << endl;
//   for (int i = 0; i < 6; i++) {
//     auto res = t.at(i);
//     cerr << "at " << res << endl;
//   }
//   cerr << endl;
// }
//
0