結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2019-06-21 14:53:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 313 ms / 3,000 ms |
コード長 | 2,184 bytes |
コンパイル時間 | 1,059 ms |
コンパイル使用メモリ | 103,596 KB |
実行使用メモリ | 8,912 KB |
最終ジャッジ日時 | 2024-12-24 21:07:07 |
合計ジャッジ時間 | 7,743 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include <cstdlib>#include <math.h>#include <cmath>#include<cctype>#include<string>#include<set>#include<iomanip>#include <map>#include<algorithm>#include <functional>#include<vector>#include<climits>#include<stack>#include<queue>#include<bitset>#include <deque>#include <climits>#include <typeinfo>#include <utility>using namespace std;using ll = long long;using R = double;using Data = pair < ll, vector <ll>>;template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;const ll MOD = 1e9 + 7;const ll inf = 1LL << 60;struct edge { ll from; ll to; ll cost; };typedef pair<ll, ll>pll;#define all(x) (x).begin(),(x).end()#define rep(i,m,n) for(ll i = m;i < n;++i)#define pb push_back#define fore(i,a) for(auto &i:a)#define rrep(i,m,n) for(ll i = m;i >= n;--i)#define INF INT_MAX/2template<typename T>struct BIT {int n;vector<T>dat;BIT(int n = 0) {initialize(n);}void initialize(int temp) {n = temp;dat.resize(n);rep(i, 0, n)dat[i] = 0;}T sum(int i) {T s = 0;while (i >= 0) {s += dat[i];i = (i & (i + 1)) - 1;}return s;}T sum_between(int i, int j) {if (i > j)return 0;return sum(j) - sum(i-1);}void plus(int i ,T x) {while (i < n) {dat[i] += x;i |= i + 1;}}int lower_bound(T x) {if (sum(n - 1) < x)return -1;else if (sum(0) >= x)return 0;int ng = 0, ok = n - 1;while (ok - ng > 1) {int mid = (ok + ng) / 2;if (sum(mid) >= x)ok = mid;else ng = mid;}return ok;}};int T[202020];ll A[202020];int main() {int Q, K;cin >> Q >> K;vector<ll>dic;rep(i, 0, Q) {cin >> T[i];if (T[i] == 1) {cin >> A[i];dic.pb(A[i]);}}sort(all(dic));dic.erase(unique(all(dic)),dic.end());BIT<ll>bitnum(dic.size());rep(i, 0, Q) {if (T[i] == 1) {ll a = A[i];int ind = lower_bound(all(dic),A[i])-dic.begin();bitnum.plus(ind, 1LL);}else {int ind = bitnum.lower_bound(K);if (ind == -1) {cout << -1 << endl;}else {bitnum.plus(ind, -1LL);cout << dic[ind] << endl;}}}return 0;}