結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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)=要素kに値xを加える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>=wとなる最小のxを求める(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;}