結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 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言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Main.d(45): Error: `st.rsum(0, mid) >= k ? ok : ng` must be surrounded by parentheses when next to operator `=`
ソースコード
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{// sumimport 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));}}