verify/yukicoder/649.test.cpp

View this file on GitHub
Last update: 2024-11-09 01:34:39+09:00
Problem: https://yukicoder.me/problems/no/649

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/649"
#include "../../src/template/template.hpp"
#include "../../src/data_structure/sorted_set.hpp"
int main(void) {
    int q, k;
    cin >> q >> k;
    SortedMultiSet st;
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            ll v;
            cin >> v;
            st.insert(v);
        } else {
            if((int)st.size() < k) {
                cout << -1 << '\n';
            } else {
                auto itr = st.find_by_order(k - 1);
                cout << *itr << '\n';
                st.erase(itr);
            }
        }
    }
}

#line 1 "verify/yukicoder/649.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/649"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 2 "src/template/policy_based_data_structure.hpp"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
#line 4 "src/data_structure/sorted_set.hpp"
using SortedSet = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
using SortedMultiSet = tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#line 4 "verify/yukicoder/649.test.cpp"
int main(void) {
    int q, k;
    cin >> q >> k;
    SortedMultiSet st;
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            ll v;
            cin >> v;
            st.insert(v);
        } else {
            if((int)st.size() < k) {
                cout << -1 << '\n';
            } else {
                auto itr = st.find_by_order(k - 1);
                cout << *itr << '\n';
                st.erase(itr);
            }
        }
    }
}