結果

問題 No.649 ここでちょっとQK!
ユーザー poohbearpoohbear
提出日時 2020-08-28 13:39:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 331 ms / 3,000 ms
コード長 3,175 bytes
コンパイル時間 2,547 ms
コンパイル使用メモリ 204,464 KB
最終ジャッジ日時 2025-01-13 15:58:35
ジャッジサーバーID
(参考情報)
judge4 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
using ll = long long;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
//typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e9;
/*
vector vec
com[k]k
*/
template<typename T>
struct Compress{
vector<T> res;
Compress(vector<T> &vec){
res = vec;
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
for(ll i=0;i<(ll)vec.size();i++){
vec[i] = lower_bound(res.begin(),res.end(),vec[i])-res.begin();
}
}
ll get(const T &x){
return lower_bound(res.begin(),res.end(),x) - res.begin();
}
const T &operator[](ll k) const{
return res[k];
}
};
/*BIT
1-indexed
add(k,x)=kx
sum(k)=a_1+a_2+...+a_k
query(l,r)=a_l+a_l+1+...a_r
lower_bound(w)=a_1+a_2+...+a_x>=wx(a_i使)
(w+1)
prll()=
*/
template<typename T>
struct BIT{
ll n;//
vector< T > data;
BIT(ll n_):n(n_+1),data(n,0){}
void add(ll k, T x){
for(ll i = k;i < n;i += (i & -i)){
data[i] += x;
}
}
T sum(ll k){
T s(0);
for(ll i = k; i > 0; i -= (i & -i)){
s += data[i];
}
return s;
}
T query(ll l,ll r){
return sum(r) - sum(l-1);
}
ll lower_bound(T w){
if(w <= 0)return 0;
else{
ll x = 0;
ll r = 1;
while(r < n) r = r << 1;
for(ll len = r; len > 0; len = len >> 1){
if(x+len<n && data[x+len]<w){
w -= data[x+len];
x += len;
}
}
return x+1;
}
}
void print(){
for(ll i=1;i<n;i++){
cout << query(i,i) << ' ';
}
cout << endl;
}
};
int main(){
ll q,k;
cin >> q >> k;
vector<P>que;
vector<ll>seen;
rep(i,q){
ll x;
cin >> x;
if(x==1){
ll y;
cin >> y;
seen.push_back(y);
que.push_back({x,y});
}
else{
que.push_back({x,0});
}
}
Compress<ll>com(seen);
BIT<ll>bit(seen.size());
rep(i,q){
if(que[i].first==1){
ll idx = com.get(que[i].second);
bit.add(idx+1,1);
}
else{
ll w = bit.lower_bound(k);
if(w==seen.size()+1)cout << -1 << endl;
else cout << com[w-1] << endl;
bit.add(w,-1);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0