Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int k = 2;
- int mas[2000001];
- int r = 0;
- void Shift_Up(int pos) {
- if (pos == 0) {
- return;
- }
- if (mas[pos] < mas[(pos - 1) / k]) {
- swap(mas[pos], mas[(pos - 1) / k]);
- Shift_Up((pos - 1) / k);
- }
- }
- void Shift_Down(int pos) {
- if (pos * k + 1 >= r) {
- return;
- }
- int min_value = mas[pos * k + 1];
- int pos_value = 1;
- for (int i = 2; i <= k; ++i) {
- if (pos * k + i < r && mas[pos * k + i] < min_value) {
- min_value = mas[pos * k + i];
- pos_value = i;
- }
- }
- swap(mas[pos], mas[pos * k + pos_value]);
- Shift_Down(pos * k + pos_value);
- }
- void insert(int x) {
- mas[r] = x;
- r++;
- Shift_Up(r - 1);
- }
- int get_min() {
- return mas[0];
- }
- int size() {
- return r;
- }
- void extract_min() {
- --r;
- swap(mas[0], mas[r]);
- Shift_Down(0);
- }
- vector <pair <string, int> > ans;
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(nullptr);
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- string s;
- cin >> s;
- if (s == "insert") {
- int x;
- cin >> x;
- insert(x);
- ans.push_back({"insert", x});
- continue;
- }
- if (s == "removeMin") {
- if (size() == 0) {
- ans.push_back({"insert", 1});
- insert(1);
- }
- extract_min();
- ans.push_back({"removeMin", 0});
- continue;
- }
- if (s == "getMin") {
- int x;
- cin >> x;
- if (size() == 0) {
- ans.push_back({"insert", x});
- insert(x);
- ans.push_back({"getMin", x});
- continue;
- }
- while (size() > 0 && get_min() < x) {
- extract_min();
- ans.push_back({"removeMin", 0});
- }
- if (size() == 0) {
- ans.push_back({"insert", x});
- insert(x);
- ans.push_back({"getMin", x});
- continue;
- }
- if (get_min() == x) {
- ans.push_back({"getMin", x});
- continue;
- }
- ans.push_back({"insert", x});
- insert(x);
- ans.push_back({"getMin", x});
- }
- }
- cout << ans.size() << endl;
- for (auto i : ans) {
- cout << i.first << ' ';
- if (i.first != "removeMin") {
- cout << i.second;
- }
- cout << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement