結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2019-12-11 10:46:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 256 ms / 3,000 ms |
コード長 | 3,327 bytes |
コンパイル時間 | 1,289 ms |
コンパイル使用メモリ | 123,128 KB |
実行使用メモリ | 9,488 KB |
最終ジャッジ日時 | 2024-06-24 07:36:51 |
合計ジャッジ時間 | 4,954 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<deque> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<cassert> using namespace std; typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; typedef long double ld; const int inf=1e9+7; const ll INF=1LL<<60 ; const ll mod=1e9+7 ; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef complex<ld> Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<int, int> P; typedef pair<ld, ld> LDP; typedef pair<ll, ll> LP; #define fr first #define sc second #define all(c) c.begin(),c.end() #define pb push_back #define debug(x) cout << #x << " = " << (x) << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } //#define int long long template <class Abel> struct BIT { private: vector<Abel> node; int n; Abel UNITY_SUM = 0; //to be set public: BIT(int n_) { n = n_; node.resize(n, UNITY_SUM); } //0-indexed void add(int a, Abel w) { for (int i = a; i < n; i |= i + 1)node[i] += w; } //[0,a) Abel sum(int a) { Abel ret = UNITY_SUM; for (int i = a - 1; i >= 0; i = (i&(i + 1)) - 1)ret += node[i]; return ret; } //[a,b) Abel sum(int a, int b) { return sum(b) - sum(a); } //k-th number (k is 0-indexed) int get(int k) { ++k; int res = 0; int n = 1; while(n < (int)node.size()) n *= 2; for(int i = n / 2; i > 0; i /= 2) { if(res + i < (int)node.size() && node[res + i - 1] < k) { k -= node[res + i - 1]; res += i; } } return res; //0-indexed } //debug void print() { for(int i = 0; i < n; ++i) cout << sum(i, i + 1) << ","; cout << endl; } }; template<typename T> vector<T> compress(vector<T> &A){ sort(A.begin(), A.end()); A.erase(unique(A.begin(), A.end()), A.end()); return A; } void solve() { int q, k; cin >> q >> k; //query先読み vector<int> query(q); vector<ll> v(q), num; rep(i, q) { cin >> query[i]; if(query[i] == 1) { cin >> v[i]; num.push_back(v[i]); } } auto ncom = compress(num); BIT<int> bit(200200); rep(i, q) { if(query[i] == 1) { int index = lower_bound(all(ncom), v[i]) - ncom.begin(); bit.add(index, 1); } else { if(bit.sum(200200) < k) { cout << -1 << endl; } else { int index = bit.get(k - 1); cout << num[index] << endl; bit.add(index, -1); } } } } signed main() { ios::sync_with_stdio(false); cin.tie(0); //cout << fixed << setprecision(10); //init(); solve(); //cout << "finish" << endl; return 0; }