結果

問題 No.2809 Sort Query
ユーザー Pres1dentPres1dent
提出日時 2024-07-14 21:44:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,516 ms / 2,000 ms
コード長 9,132 bytes
コンパイル時間 8,270 ms
コンパイル使用メモリ 320,032 KB
実行使用メモリ 42,652 KB
最終ジャッジ日時 2024-07-14 21:46:00
合計ジャッジ時間 96,949 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1,134 ms
40,832 KB
testcase_02 AC 1,084 ms
40,832 KB
testcase_03 AC 1,085 ms
40,824 KB
testcase_04 AC 1,095 ms
40,704 KB
testcase_05 AC 1,046 ms
40,832 KB
testcase_06 AC 1,131 ms
40,704 KB
testcase_07 AC 1,096 ms
40,756 KB
testcase_08 AC 1,117 ms
40,880 KB
testcase_09 AC 1,082 ms
40,680 KB
testcase_10 AC 1,102 ms
40,704 KB
testcase_11 AC 1,199 ms
42,532 KB
testcase_12 AC 1,100 ms
42,528 KB
testcase_13 AC 1,148 ms
42,396 KB
testcase_14 AC 1,129 ms
42,400 KB
testcase_15 AC 1,149 ms
42,400 KB
testcase_16 AC 1,141 ms
42,528 KB
testcase_17 AC 1,099 ms
42,400 KB
testcase_18 AC 1,134 ms
42,528 KB
testcase_19 AC 1,146 ms
42,528 KB
testcase_20 AC 1,166 ms
42,400 KB
testcase_21 AC 1,175 ms
42,400 KB
testcase_22 AC 1,197 ms
42,492 KB
testcase_23 AC 1,200 ms
42,528 KB
testcase_24 AC 1,198 ms
42,404 KB
testcase_25 AC 1,247 ms
42,652 KB
testcase_26 AC 1,361 ms
40,792 KB
testcase_27 AC 1,391 ms
40,704 KB
testcase_28 AC 1,390 ms
40,812 KB
testcase_29 AC 1,355 ms
40,960 KB
testcase_30 AC 1,367 ms
40,756 KB
testcase_31 AC 1,312 ms
40,704 KB
testcase_32 AC 1,291 ms
40,832 KB
testcase_33 AC 1,288 ms
40,704 KB
testcase_34 AC 1,265 ms
40,832 KB
testcase_35 AC 1,286 ms
40,832 KB
testcase_36 AC 1,100 ms
42,400 KB
testcase_37 AC 1,102 ms
42,532 KB
testcase_38 AC 1,103 ms
42,532 KB
testcase_39 AC 1,132 ms
42,396 KB
testcase_40 AC 1,085 ms
42,400 KB
testcase_41 AC 1,478 ms
40,832 KB
testcase_42 AC 1,482 ms
40,832 KB
testcase_43 AC 1,454 ms
40,832 KB
testcase_44 AC 1,461 ms
40,704 KB
testcase_45 AC 1,516 ms
40,676 KB
testcase_46 AC 1,221 ms
40,832 KB
testcase_47 AC 1,193 ms
40,704 KB
testcase_48 AC 1,191 ms
40,704 KB
testcase_49 AC 1,269 ms
40,704 KB
testcase_50 AC 1,175 ms
40,704 KB
testcase_51 AC 1,311 ms
24,320 KB
testcase_52 AC 1,198 ms
24,320 KB
testcase_53 AC 1,199 ms
24,320 KB
testcase_54 AC 1,301 ms
24,320 KB
testcase_55 AC 1,209 ms
24,316 KB
testcase_56 AC 881 ms
24,576 KB
testcase_57 AC 793 ms
18,944 KB
testcase_58 AC 650 ms
20,992 KB
testcase_59 AC 702 ms
16,000 KB
testcase_60 AC 743 ms
34,176 KB
testcase_61 AC 960 ms
40,192 KB
testcase_62 AC 753 ms
19,840 KB
testcase_63 AC 891 ms
26,368 KB
testcase_64 AC 1,140 ms
39,680 KB
testcase_65 AC 631 ms
28,544 KB
testcase_66 AC 2 ms
6,940 KB
testcase_67 AC 2 ms
6,944 KB
testcase_68 AC 2 ms
6,940 KB
testcase_69 AC 2 ms
6,940 KB
testcase_70 AC 1 ms
6,944 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) ok
//   - split
//   - merge
// .exist(value)  ok
// .erase(value)  ok
// .dump          ok
// .size()        ok
// .at(index) i the element  ok
// .upper_bound(value)  ok
// .lower_bound(value)  ok
// 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:
  explicit Treap(void) : Treap(vector<T>()) {}
  explicit Treap(vector<T> v) {
    for (T e : v) {
      insert(e);
    }
  }
  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;
  map<int, ll> mp;
  rep(i, n) mp[i] = A[i];
  bool first = true;
  rep(i, q) {
//     cerr << t.size() << endl;
    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) {
      if (first) {
        for (auto [k, v] : mp) {
          A[k] = v;
        }
        t = Treap(A);
        first = false;
        mp = {};
      } else {
        vector<ll> tmp;
        for (auto [k, v] : mp) {
          auto res = t.at(k);
          tmp.push_back(t.at(k));
        }
        for (auto e : tmp) {
          assert(t.exist(e));
          t.erase(e);
        }
        for (auto [k, v] : mp) {
          t.insert(v);
        }
        mp = {};
      }
    } else {
      int k; cin >> k;
      k--;
      if (mp.find(k) == mp.end()) {
        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