結果
問題 |
No.3167 [Cherry 7th Tune C] Cut in Queue
|
ユーザー |
![]() |
提出日時 | 2025-06-16 20:18:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 236 ms / 2,500 ms |
コード長 | 1,899 bytes |
コンパイル時間 | 2,326 ms |
コンパイル使用メモリ | 206,928 KB |
実行使用メモリ | 47,628 KB |
最終ジャッジ日時 | 2025-06-16 20:18:43 |
合計ジャッジ時間 | 12,162 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x) #define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x) #define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x) #define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x) #define int ll typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #ifndef DB #define DB 0 #define endl '\n' #endif #define debugl(l) if constexpr ((l) < DB) #define debug debugl(0) const int N = 300'010*2; struct Fen { vector<int> a; int n; void init(int sz) { n = sz; a.assign(n+1, {}); } void add(int i) { i++; while (i <= n) { a[i]++; i += i&-i; } } int index(int x) { int p = 1<<__lg(n); int i = 0; while (p) { if (i + p <= n && x >= a[i + p]) { x -= a[i + p]; i += p; } p /= 2; } return i; } }; void solve() { int n; cin >> n; vector<int> a(n); for (auto &x : a) { cin >> x; x--; } int q; cin >> q; vector<pii> qu(q); for (auto &[x, y] : qu) { cin >> x; if (x != 2) { cin >> y; y--; } } list<int> ls; vector<list<int>::iterator> its(n); for (int x : a) its[x] = ls.insert(ls.end(), x); for (auto [t, p] : qu) { if (t != 1) continue; auto it = p == -1? ls.end(): its[p]; its.push_back(ls.insert(it, its.size())); } vector<int> b(ls.begin(), ls.end()); n = b.size(); vector<int> bp(n); Loop (i,0,n) bp[b[i]] = i; debug { for (int x : b) cerr << x << ' '; cerr << "???\n"; } Fen fen; fen.init(n); for (int x : a) fen.add(bp[x]); int base = 0; int cnt = a.size(); for (auto [t, p] : qu) { if (t == 1) fen.add(bp[cnt++]); if (t == 2) base++; if (t == 3) { int i = fen.index(base + p); debug cerr << i << "!\n"; cout << b[i] + 1 << '\n'; } } } signed main() { cin.tie(0) -> sync_with_stdio(false); int t = 1; //cin >> t; while (t--) solve(); }