#747657 (C++17) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	eQe
提出日時	2022-03-23 08:21:58
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,159 bytes
コンパイル時間	4,357 ms
コンパイル使用メモリ	268,100 KB
実行使用メモリ	12,100 KB
最終ジャッジ日時	2024-04-19 13:21:40
合計ジャッジ時間	8,276 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,944 KB
testcase_02	WA	-
testcase_03	AC	27 ms 7,036 KB
testcase_04	WA	-
testcase_05	AC	77 ms 12,100 KB
testcase_06	WA	-
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	1 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	50 ms 7,668 KB
testcase_13	AC	49 ms 7,672 KB
testcase_14	AC	50 ms 7,672 KB
testcase_15	AC	50 ms 7,668 KB
testcase_16	AC	49 ms 7,540 KB
testcase_17	AC	56 ms 7,872 KB
testcase_18	AC	58 ms 8,084 KB
testcase_19	AC	64 ms 8,324 KB
testcase_20	AC	69 ms 8,496 KB
testcase_21	AC	73 ms 10,852 KB
testcase_22	AC	79 ms 10,948 KB
testcase_23	AC	85 ms 11,256 KB
testcase_24	AC	91 ms 11,484 KB
testcase_25	AC	96 ms 11,804 KB
testcase_26	AC	100 ms 11,980 KB
testcase_27	AC	2 ms 6,940 KB
testcase_28	AC	1 ms 6,944 KB
testcase_29	AC	1 ms 6,940 KB
testcase_30	AC	39 ms 6,940 KB
testcase_31	AC	38 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB
testcase_33	AC	1 ms 6,940 KB
testcase_34	AC	2 ms 6,940 KB
testcase_35	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<atcoder/all>
using namespace atcoder;
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fin(a) {pt(a);return 0;}
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
template<class T>T popcnt(T a){return __builtin_popcountll(a);}
template<class T>using ascending_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>using descending_priority_queue=priority_queue<T>;
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,const T&b){if(b<a){a=b;return 1;}return 0;}
template<typename V,typename T>T max(vector<V>&vec,const T&id){T r=id;for(auto&v:vec)chmax(r,max(v,id));return r;}
template<typename V,typename T>T min(vector<V>&vec,const T&id){T r=id;for(auto&v:vec)chmin(r,min(v,id));return r;}
istream&operator>>(istream&is,modint1000000007&x){unsigned int t;is>>t;x=t;return is;}
istream&operator>>(istream&is,modint998244353&x){unsigned int t;is>>t;x=t;return is;}
istream&operator>>(istream&is,modint&x){unsigned int t;is>>t;x=t;return is;}
ostream&operator<<(ostream&os,const modint1000000007&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint998244353&x){os<<x.val();return os;}
ostream&operator<<(ostream&os,const modint&x){os<<x.val();return os;}
template<class T1,class T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<class T1,class T2>ostream&operator<<(ostream&os,const pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}
template<class T>istream&operator>>(istream&is,vector<T>&v){for(T&x:v)is>>x;return is;}
template<class T>ostream&operator<<(ostream&os,const vector<T>&v){for(int i=0;i<(int)v.size();i++){os<<v[i]<<(i+1==v.size()?"":" ");}return os;}
template<class...A>void pt_rest(){cout<<'\n';}
template<class...A>void pt(){cout<<'\n';}
template<class T,class...A>void pt_rest(const T&first,const A&...rest){cout<<" "<<first;pt_rest(rest...);}
template<class T,class...A>void pt(const T&first,const A&...rest){cout<<first;pt_rest(rest...);}
template<typename V,typename H>void resize(vector<V>&vec,const H head){vec.resize(head);}
template<typename V,typename H,typename...T>void resize(vector<V>&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);}
template<typename V,typename T>void fill(V&x,const T&val){x=val;}
template<typename V,typename T>void fill(vector<V>&vec,const T&val){for(auto&v:vec)fill(v,val);}
template<typename H>void vin(istream&is,const int idx,vector<H>&head){is>>head[idx];}
template<typename H,typename...T>void vin(istream&is,const int idx,vector<H>&head,T&...tail){vin(is>>head[idx],idx,tail...);}
template<typename H,typename...T>void vin(istream&is,vector<H>&head,T&...tail){for(int i=0;i<(int)head.size();i++)vin(is,i,head,tail...);}
template<typename H,typename...T>void vin(vector<H>&head,T&...tail){vin(cin,head,tail...);}
void divisor(ll n,map<ll,ll>&div){for(ll i=1;i*i<=n;i++)if(n%i==0){div[i]++;div[n/i]++;}}
void factrization(ll n,map<ll,ll>&fact){for(ll i=2;i*i<=n;i++)while(n%i==0){fact[i]++;n/=i;}if(n>1)fact[n]++;}
ll lsqrt(ll x){ll r=sqrt(x)-1;while((r+1)<=x/(r+1))r++;return r;};
ll inf=1e18+7;
ld pi=acos(-1);
ld eps=1e-10;
using v1=vector<ll>;
using v2=vector<v1>;
using v3=vector<v2>;
using v4=vector<v3>;
using S=ll;
S op(S a,S b){return a+b;}
S e(){return 0;}

v1 compress(v1&C){
  v1 res;
  ll n=C.size();
  for(ll i=0;i<n;i++)for(ll d=0;d<1;d++)res.push_back(C[i]+d);
  sort(all(res));
  res.erase(unique(all(res)),res.end());
  for(ll i=0;i<n;i++)C[i]=lower_bound(all(res),C[i])-res.begin();
  return res;
}

ll Q,K;
bool f(S x){return x<K;}

int main(void){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  
  cin>>Q>>K;
  v1 v(Q,inf);
  for(ll i=0;i<Q;i++){
    ll _;cin>>_;
    if(_==1)cin>>v[i];
  }
  
  v1 val=compress(v);
  segtree<S,op,e>seg(vector<S>(val.size(),0));
  for(ll i=0;i<Q;i++){
    if(val[v[i]]<inf){
      seg.set(v[i],seg.get(v[i])+1);
    }else{
      if(seg.all_prod()<K)pt(-1);
      else{
        ll k=seg.max_right<f>(0);
        seg.set(k,seg.get(k)-1);
        pt(val[k]);
      }
    }
  }
}

yukicoder

結果

テストケース

ソースコード