Hướng dẫn giải của Bedao Mini Contest 18 - SORTQUERY


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

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 ^^

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.