#995051 (C++17) No.2809 Sort Query

提出ソース

結果

問題	No.2809 Sort Query
ユーザー	Pres1dent
提出日時	2024-07-14 20:42:18
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,665 bytes
コンパイル時間	7,574 ms
コンパイル使用メモリ	319,712 KB
実行使用メモリ	41,400 KB
最終ジャッジ日時	2024-07-14 20:44:03
合計ジャッジ時間	96,267 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-
testcase_46	WA	-
testcase_47	WA	-
testcase_48	WA	-
testcase_49	WA	-
testcase_50	WA	-
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	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	WA	-
testcase_68	WA	-
testcase_69	WA	-
testcase_70	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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 {
    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;
  }
  // 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 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 == 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 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);
    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;
  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<int> tmp;
      for (auto [k, v] : mp) {
//         cerr << "i, n, k, size " << i << " " << n << " " << k << " " << t.size() << endl;
        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()) {
//         cerr << "n, k, size " << i << " " << n << " " << k << " " << t.size() << endl;
        cout << t.at(k) << endl;
      } else {
        cout << mp[k] << endl;
      }
    }
  }
  
}
// int main() {
//   solve();
//   return 0;
//   Treap<int> t;
//   t.insert(3);
//   t.insert(3);
//   t.insert(4);
//   t.insert(5);
//   t.erase(2);
//   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;
//   t.erase(5);
//   for (int i = 0; i < n; i++) {
//     cerr << t.exist(i) << " ";
//   }
//   cerr << 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;
// }

yukicoder

結果

テストケース

ソースコード