Subtask ~1~: ~O(Q^2 \times \log(Q))~.

Ta sẽ dùng lưu mảng ~A~ bằng một std::vector trong C++ hay cấu trúc dữ liệu nào khác hỗ trợ thao tác xoá, thêm và sắp xếp. Thực ra không phải lúc nào truy vấn thứ ~3~ cũng thực hiện nên thời gian chạy sẽ nhỏ hơn rất nhiều.

Subtask ~2~: ~O(Q \times \log(Q))~.

Ta duy trì hai mảng riêng biệt ~A~, ~B~.

Nếu gặp truy vấn ~1~: Ta thêm ~x~ vào ~B~.

Nếu gặp truy vấn ~2~: Nếu ~A~ không rỗng thì ta in ra phần tử đầu tiên của ~A~, ngược lại in ra phần tử đầu tiên của ~B~. Xoá phần tử đó.

Nếu gặp truy vấn ~3~: Ta sẽ hợp nhất ~B~ vào ~A~, sau đó xoá ~B~ và sắp xếp lại ~A~.

Để cách làm trên chạy được trong giới hạn đề bài thì mảng ~A~ phải hỗ trợ thao tác sắp xếp các phần tử nhanh. Do đó ta chọn sử dụng ~A~ là std::set và ~B~ là std::vector.

Code mẫu

#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
using ll = long long;

const int inf = 1061109567;
const ll INF = 4557430888798830399;
const int MOD = 998244353;

int query;
multiset <pair<ll, int>> ms;

int32_t main(void) {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(".in", "r")) {
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> query;
    for (ll i = 2e9; i < query + 2e9; ++ i) {
        int type;
        cin >> type;
        if (type == 1) {
            int u; cin >> u;
            ms.insert({i, u});
        } else if (type == 2) {
            cout << ms.begin()->second << "\n";
            ms.erase(ms.begin());
        } else {
            while (ms.size() && ms.rbegin()->first >= 2e9) {
                int u = ms.rbegin()->second;
                ms.erase(-- ms.end());
                ms.insert({u, u});
            }
        }
    }
    return 0;
}

// Written by Kazama Hoang ^^