結果

問題 No.2809 Sort Query
ユーザー Pres1dent
提出日時 2024-07-14 16:05:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 5,675 bytes
コンパイル時間 6,630 ms
コンパイル使用メモリ 310,540 KB
最終ジャッジ日時 2025-02-22 06:40:30
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 3 RE * 67
権限があれば一括ダウンロードができます

ソースコード

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 {
    int key, pri, sz;
    Node *l, *r;
    Node(int 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;
  }
  void split(Node *&t, T key, Node *&l, Node *&r) {
    if (!t) {
      l = r = nullptr;
    } else if (key < t->key) {
      split(t->l, key, l, t->l);
      r = t;
    } else {
      split(t->r, key, t->r, r);
      l = t;
    }
    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 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 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) const {
    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);
    }
  }

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);
  }
};


int main() {
  int n, q; cin >> n >> q;
  vector<int> A(n); rep(i, n) cin >> A[i];
  Treap<int> t;
  rep(i, n) t.insert(A[i]);
  map<int, int> mp;
  rep(i, q) {
    int op; cin >> op;
    if (op == 1) {
      int k, x; cin >> k >> x;
      k--;
      mp[k] = x;
    } else if (op == 2) {
      vector<int> tmp;
      for (auto [k, v] : mp) {
        tmp.push_back(t.at(k));
      }
      for (auto e : tmp) {
        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