結果

問題 No.649 ここでちょっとQK!
ユーザー ikdikd
提出日時 2018-02-09 23:55:51
言語 D
(dmd 2.109.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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0