結果

問題 No.3167 [Cherry 7th Tune C] Cut in Queue
ユーザー The Forsaking
提出日時 2025-05-31 12:34:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 442 ms / 2,500 ms
コード長 2,387 bytes
コンパイル時間 1,893 ms
コンパイル使用メモリ 195,508 KB
実行使用メモリ 21,016 KB
最終ジャッジ日時 2025-05-31 12:34:30
合計ジャッジ時間 16,194 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:94:46: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   94 |         for (int i = 1; i < n + 1; i++) scanf("%d", w + i), insert(w[i]);
      |                                         ~~~~~^~~~~~~~~~~~~
main.cpp:100:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  100 |                 scanf("%d", &op);
      |                 ~~~~~^~~~~~~~~~~
main.cpp:102:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |                         scanf("%d", &v);
      |                         ~~~~~^~~~~~~~~~
main.cpp:111:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  111 |                         scanf("%d", &v);
      |                         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];


struct Node {
    int s[2], v, p;
    int size;
    void init(int _v, int _p){ v = _v, p = _p, size = 1; }
}tr[N];
int root, idx, id[N];

void pushup(int u) { tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1; }

void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[y == tr[z].s[1]] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[y].s[k]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        rotate(x);
    }
    if (!k) root = x;
}

void insert(int v) {
    int u = root, p = 0;
    while (u) p = u, u = tr[u].s[1];
    u = ++idx;
	if (abs(v) != INF) id[v] = u;
    if (p) tr[p].s[1] = u;
    tr[u].init(v, p);
    splay(u, 0);
}

void insert(int u, int v) {
	splay(u, 0);
	int l = tr[u].s[0];
	while (tr[l].s[1]) l = tr[l].s[1];
	splay(l, 0);
	splay(u, l);
	int nu = ++idx;
	id[v] = nu;
	tr[u].s[0] = nu;
	tr[nu].init(v, u);
	pushup(u), pushup(l);
	splay(nu, 0);
}

int get_k(int k) {
    int u = root;
    while (u) {
        if (tr[tr[u].s[0]].size >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].size + 1 == k) {
			splay(u, 0);
			return u;
		}
        else k -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];
    }
    assert(0);
    return -1;
}

void erase(int u) {
    splay(u, 0);
    int l = tr[u].s[0], r = tr[u].s[1];
    while (tr[l].s[1]) l = tr[l].s[1];
    while (tr[r].s[0]) r = tr[r].s[0];
    splay(l, 0), splay(r, l);
    tr[r].s[0] = 0;
    pushup(r), pushup(l);
}


int main() {
	insert(-INF);
	cin >> n;
	for (int i = 1; i < n + 1; i++) scanf("%d", w + i), insert(w[i]);
	insert(INF);
	cin >> m;
	int t = n + 1;
	while (m--) {
		int op, v;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d", &v);
			int u = v ? id[v] : n + 2;
			insert(u, t++);
		} else if (op == 2) {
			splay(1, 0);
			int l = tr[1].s[1];
			while (tr[l].s[0]) l = tr[l].s[0];
			erase(l);
		} else {
			scanf("%d", &v);
			printf("%d\n", tr[get_k(v + 1)].v);
		}
	}
	return 0;
}
0