結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
|
提出日時 | 2018-02-09 22:40:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 126 ms / 3,000 ms |
コード長 | 1,258 bytes |
コンパイル時間 | 1,513 ms |
コンパイル使用メモリ | 166,172 KB |
実行使用メモリ | 9,552 KB |
最終ジャッジ日時 | 2024-10-08 16:26:26 |
合計ジャッジ時間 | 4,837 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:40:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | scanf("%d%d",&q,&k); | ~~~~~^~~~~~~~~~~~~~ main.cpp:42:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 42 | scanf("%d",&type[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:44:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | scanf("%lld",&v[i]); | ~~~~~^~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define MOD 1000000007LLusing namespace std;typedef long long ll;typedef pair<int,int> P;class segtree{public:static const int N=1<<18;int dp[1<<19];segtree(){memset(dp,0,sizeof(dp));}void update(int k,int v){k+=N-1;dp[k]+=v;while(k>0){k=(k-1)/2;dp[k]=dp[k*2+1]+dp[k*2+2];}}int query(int a,int b,int k=0,int l=0,int r=N){if(b<=l || r<=a)return 0;if(a<=l && r<=b)return dp[k];int mid=(l+r)/2;int vl=query(a,b,k*2+1,l,mid);int vr=query(a,b,k*2+2,mid,r);return vl+vr;}};int q,k;int type[200005];ll v[200005];vector<ll> vec;segtree seg;int main(void){scanf("%d%d",&q,&k);for(int i=0;i<q;i++){scanf("%d",&type[i]);if(type[i]==1){scanf("%lld",&v[i]);vec.push_back(v[i]);}}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());for(int i=0;i<q;i++){if(type[i]==1){int lv=lower_bound(vec.begin(),vec.end(),v[i])-vec.begin();seg.update(lv,1);}else{if(seg.query(0,seg.N)<k){puts("-1");}else{int l=0,r=seg.N;while(l+1<r){int mid=(l+r)/2;if(seg.query(0,mid)>=k)r=mid;else l=mid;}printf("%lld\n",vec[r-1]);seg.update(r-1,-1);}}}return 0;}