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.
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ả:
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