結果

問題 No.649 ここでちょっとQK！
ユーザー ikdikd
提出日時 2018-02-09 23:55:51
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,843 bytes
コンパイル時間 54 ms
コンパイル使用メモリ 6,912 KB
最終ジャッジ日時 2024-11-14 20:20:41
合計ジャッジ時間 852 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Main.d(45): Error: `st.rsum(0, mid) >= k ? ok : ng` must be surrounded by parentheses when next to operator `=`

ソースコード

diff # 

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  import std.typecons;

  int n, k; rd(n, k);
  alias T=Tuple!(int, "t", long, "v");
  auto que=new T[](n);
  foreach(i; 0..n){
    auto args=readln.split.to!(long[]);
    if(args.length==1) que[i].t=2;
    else que[i].t=1, que[i].v=args[$-1];
  }

  int[long] compression(T[] q){
    long[] vs;
    foreach(e; q)if(e.t==1) vs~=e.v;
    sort(vs);
    int[long] ret;
    foreach(v; vs){
      if(v in ret) continue;
      ret[v]=to!(int)(ret.length);
    }
    return ret;
  }
  long[int] inv_(int[long] map){
    long[int] ret;
    foreach(v; map.keys){
      ret[map[v]]=v;
    }
    return ret;
  }

  auto map=compression(que),
       inv=inv_(map),
       m=to!(int)(map.length),
       st=new SegT(m),
       cur=0;
  foreach(e; que){
    if(e.t==1) st.add(map[e.v], 1), cur++;
    else if(cur<k) writeln(-1);
    else{
      auto ng=0, ok=m;
      while(ok-ng>1){
        auto mid=(ok+ng)/2;
        st.rsum(0, mid)>=k ? ok : ng = mid;
      }
      writeln(inv[ok-1]);
      st.add(ok-1, -1);
      cur--;
    }
  }
}

class SegT{// sum
  import std.algorithm;
  int sz=1;
  int[] seg;
  this(int n){
    while(sz<n) sz*=2;
    seg.length=(sz*2-1);
  }
  void add(int i, int x){
    i+=sz-1;
    seg[i]+=x;
    while(i>0){
      i=(i-1)/2;
      seg[i]=seg[i*2+1]+seg[i*2+2];
    }
  }
  int rsum(int l, int r, int i, int il, int ir){
    if(l<=il && ir<=r) return seg[i];
    if(ir<=l || r<=il) return 0;
    auto m=(il+ir)/2,
         vl=rsum(l, r, i*2+1, il, m),
         vr=rsum(l, r, i*2+2, m, ir);
    return vl+vr;
  }
  int rsum(int l, int r){
    return rsum(l, r, 0, 0, sz);
  }
}
void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
0