結果

問題 No.2809 Sort Query
ユーザー Pres1dentPres1dent
提出日時 2024-07-14 21:47:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,410 ms / 2,000 ms
コード長 6,799 bytes
コンパイル時間 7,663 ms
コンパイル使用メモリ 319,216 KB
実行使用メモリ 42,532 KB
最終ジャッジ日時 2024-07-22 14:14:20
合計ジャッジ時間 94,304 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1,059 ms
40,704 KB
testcase_02 AC 921 ms
40,676 KB
testcase_03 AC 997 ms
40,832 KB
testcase_04 AC 929 ms
40,704 KB
testcase_05 AC 949 ms
40,832 KB
testcase_06 AC 947 ms
40,704 KB
testcase_07 AC 969 ms
40,808 KB
testcase_08 AC 993 ms
40,704 KB
testcase_09 AC 989 ms
40,832 KB
testcase_10 AC 974 ms
40,832 KB
testcase_11 AC 997 ms
42,524 KB
testcase_12 AC 1,008 ms
42,404 KB
testcase_13 AC 993 ms
42,532 KB
testcase_14 AC 1,080 ms
42,528 KB
testcase_15 AC 998 ms
42,532 KB
testcase_16 AC 1,039 ms
42,476 KB
testcase_17 AC 1,042 ms
42,528 KB
testcase_18 AC 1,021 ms
42,528 KB
testcase_19 AC 1,069 ms
42,528 KB
testcase_20 AC 1,136 ms
42,524 KB
testcase_21 AC 1,111 ms
42,400 KB
testcase_22 AC 1,158 ms
42,524 KB
testcase_23 AC 1,079 ms
42,524 KB
testcase_24 AC 1,124 ms
42,528 KB
testcase_25 AC 1,102 ms
42,400 KB
testcase_26 AC 1,186 ms
40,760 KB
testcase_27 AC 1,236 ms
40,832 KB
testcase_28 AC 1,244 ms
40,704 KB
testcase_29 AC 1,218 ms
40,832 KB
testcase_30 AC 1,252 ms
40,704 KB
testcase_31 AC 1,165 ms
40,832 KB
testcase_32 AC 1,218 ms
40,832 KB
testcase_33 AC 1,132 ms
40,832 KB
testcase_34 AC 1,175 ms
40,832 KB
testcase_35 AC 1,185 ms
40,832 KB
testcase_36 AC 1,001 ms
42,400 KB
testcase_37 AC 1,270 ms
42,524 KB
testcase_38 AC 974 ms
42,528 KB
testcase_39 AC 1,152 ms
42,404 KB
testcase_40 AC 991 ms
42,404 KB
testcase_41 AC 1,410 ms
40,704 KB
testcase_42 AC 1,330 ms
40,784 KB
testcase_43 AC 1,381 ms
40,704 KB
testcase_44 AC 1,281 ms
40,832 KB
testcase_45 AC 1,232 ms
40,832 KB
testcase_46 AC 1,035 ms
40,832 KB
testcase_47 AC 1,224 ms
40,832 KB
testcase_48 AC 1,146 ms
40,832 KB
testcase_49 AC 1,050 ms
40,832 KB
testcase_50 AC 1,047 ms
40,704 KB
testcase_51 AC 1,152 ms
24,448 KB
testcase_52 AC 1,070 ms
24,448 KB
testcase_53 AC 1,076 ms
24,320 KB
testcase_54 AC 1,075 ms
24,448 KB
testcase_55 AC 1,095 ms
24,320 KB
testcase_56 AC 884 ms
24,448 KB
testcase_57 AC 714 ms
18,944 KB
testcase_58 AC 690 ms
21,120 KB
testcase_59 AC 731 ms
16,000 KB
testcase_60 AC 750 ms
34,048 KB
testcase_61 AC 807 ms
40,320 KB
testcase_62 AC 726 ms
19,840 KB
testcase_63 AC 822 ms
26,368 KB
testcase_64 AC 989 ms
39,680 KB
testcase_65 AC 604 ms
28,544 KB
testcase_66 AC 4 ms
5,376 KB
testcase_67 AC 2 ms
5,376 KB
testcase_68 AC 3 ms
5,376 KB
testcase_69 AC 3 ms
5,376 KB
testcase_70 AC 2 ms
5,376 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; }


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) {
    if (!t) {
      l = r = nullptr;
    } else if (key < t->key) {
      r = t;
      split(t->l, key, l, r->l);
    } else {
      l = t;
      split(t->r, key, l->r, r);
    }
    update(l), update(r);
  }
  void insert(Node *&t, Node *v) {
    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);
    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);
    for (auto v : debug) {
      int cnt = 0;
      int sz = 0;
      for (auto e : v) {
        if (e != -1) {
          sz += 1;
        }
      }
      cerr << "size " << sz << " ";
      for (auto e : v) {
        cerr << e << " ";
      }
      cerr << endl;
    }
  }
};

int main() {
  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) {
    int op; cin >> op;
    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;
      }
    }
  }
}
0