結果
問題 | No.649 ここでちょっとQK! |
ユーザー |
![]() |
提出日時 | 2019-07-26 03:21:06 |
言語 | Nim (2.2.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,835 bytes |
コンパイル時間 | 1,386 ms |
コンパイル使用メモリ | 85,828 KB |
最終ジャッジ日時 | 2024-07-02 06:22:30 |
合計ジャッジ時間 | 3,873 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
/home/judge/data/code/Main.nim(81, 7) Error: invalid pragma: this: self
ソースコード
#{{{ headerimport algorithm, sequtils, tables, macros, math, sets, strutilswhen defined(MYDEBUG):import headerproc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}proc getchar(): char {.header: "<stdio.h>", varargs.}proc nextInt(): int = scanf("%lld",addr result)proc nextFloat(): float = scanf("%lf",addr result)proc nextString(): string =var get = falseresult = ""while true:var c = getchar()if int(c) > int(' '):get = trueresult.add(c)else:if get: breakget = falsetemplate `max=`*(x,y:typed):void = x = max(x,y)template `min=`*(x,y:typed):void = x = min(x,y)template infty(T): untyped = ((T(1) shl T(sizeof(T)*8-2)) - 1)#}}}import randomvarrnd = initRand(2019)#type Xor128 = object# x,y,z,w:int##proc newXor128():Xor128 =# return Xor128(x:123456789,y:362436069, z:521288629, w:88675123)##proc next(a:var Xor128):int =# var# x:ref int# y:ref int# z:ref int# w:ref int# x[] = a.x# y[] = a.y# z[] = a.z# w[] = a.w# var# t = x[] xor (x[] shl 11)# x[] = y[]# y[] = z[]# z[] = w[]# w[] = (w[] xor (w[] shr 19)) xor (t xor (t shr 8))# return w[]#template< class S, class T = S >#struct RandomizedBinarySearchTree {## using F = function< S(S, S) >;## using G = function< S(S, T) >;## using H = function< T(T, T) >;## using P = function< T(T, int) >;##typeNode[S,T] = ref objectl,r: Node[S,T]cnt: intkey, sum: Slazy: TRBST[S,T] = ref object of RootObjM1: SOM0: Tf: proc(x,y:S):Sg: proc(x:S,y:T):Sh: proc(x,y:T):Tp: proc(x:T,y:int):T{.this: self.}proc newNode[S, T](k:S, p:T): Node[S, T] =return Node[S, T](cnt:1, key:k, sum:k, lazy:p, l:nil, r:nil)proc newRBST[S](f:proc(x,y:S):S, M1:S):RBST[S, S] =return RBST[S, S](M1:M1,f:f)#proc newRBST[S, T](M1:S, OM0:T):RBST[S, T] =# return RBST[S, T](M1:M1,OM0:OM0)proc alloc[S, T](self:RBST[S,T], key:S):Node[S,T] =return newNode[S,T](key, self.OM0)proc clone[S,T](self:RBST[S,T], t:Node[S,T]):Node[S,T] =return tproc count[S,T](self:RBST[S,T], t:Node):int =if t != nil: return t.cntelse: return 0proc sum[S,T](self:RBST[S,T], t:Node[S,T]):S =if t != nil: return t.sumelse: return self.M1proc update[S,T](self:RBST[S,T], t:Node[S,T]):Node[S,T] =t.cnt = count(t.l) + count(t.r) + 1t.sum = self.f(self.f(sum(t.l), t.key), sum(t.r))return tproc propagate[S,T](self:RBST[S,T], t2:Node[S,T]):Node[S,T] =var t = clone(t2)if t.lazy != self.OM0:t.key = self.g(t.key, t.lazy)if t.l!=nil:t.l = clone(t.l)t.l.lazy = self.h(t.l.lazy, t.lazy)t.l.sum = self.f(t.l.sum, self.p(t.lazy, count(t.l)))if t.r != nil:t.r = clone(t.r)t.r.lazy = self.h(t.r.lazy, t.lazy)t.r.sum = self.f(self.p(t.lazy, count(t.r)), t.r.sum)t.lazy = self.OM0return update(t)proc merge[S,T](self:RBST[S,T], l2,r2: Node[S,T]): Node[S,T] =if l2 == nil:return r2elif r2 == nil:return l2varl = l2r = r2if rnd.rand(0..10^18) mod (l.cnt + r.cnt) < l.cnt:l = self.propagate(l)l.r = self.merge(l.r, r)return update(l)else:r = self.propagate(r);r.l = self.merge(l, r.l)return update(r);proc split[S,T](self:RBST[S,T], t:var Node[S,T], k:int):(Node[S,T],Node[S,T]) =if t == nil:return (nil,nil)t = self.propagate(t);if k <= count(t.l):var s = self.split(t.l, k)t.l = s[1]return (s[0], self.update(t))else:var s = self.split(t.r, k - self.count(t.l) - 1)t.r = s[0]return (update(t), s[1])proc build[S,T](self:RBST[S,T],l,r:int, v: seq[S]):Node[S,T] =if l + 1 >= r: return self.alloc(v[l])varnl = self.build(l, (l + r) shr 1, v)nr = self.build((l + r) shr 1, r, v)return self.merge(nl, nr)proc build[S,T](self:RBST[S,T], v: seq[S]):Node[S,T] =return self.build(0, v.len, v)## vector< Node > pool;# int ptr;## const S M1;# const T OM0;# const F f;# const G g;# const H h;# const P p;## RandomizedBinarySearchTree(int sz, const F &f, const S &M1) :# pool(sz), ptr(0), f(f), g(G()), h(H()), p(P()), M1(M1), OM0(T()) {}## RandomizedBinarySearchTree(int sz, const F &f, const G &g, const H &h, const P &p,# const S &M1, const T &OM0) :# pool(sz), ptr(0), f(f), g(g), h(h), p(p), M1(M1), OM0(OM0) {}###proc dump[S,T](self:RBST[S,T], r:var Node[S,T], i:var int, v:var seq[S]):void =if r == nil:returnr = self.propagate(r)self.dump(r.l, i, v)v[i] = r.keyi += 1self.dump(r.r, i, v)proc dump[S,T](self:RBST[S,T], r:var Node[S,T]):seq[S] =result = newSeq[S](self.count(r))var i = 0self.dump(r, i, result)proc to_string[S,T](self:RBST[S,T], r:var Node[S,T]):string =var s = self.dump(r)result = ""for i in 0..<s.len:result.add(", ")proc insert[S,T](self:RBST[S,T], t: var Node[S,T], k:int, v:S):void =varx = self.split(t, k)t = self.merge(self.merge(x[0], self.alloc(v)), x[1])proc erase[S,T](self:RBST[S,T], t: var Node[S,T], k:int):void =var x = self.split(t, k);t = self.merge(x[0], self.split(x[1], 1)[1])proc query[S,T](self:RBST[S,T], t: var Node[S,T], a,b:int):S =varx = self.split(t, a)y = self.split(x[1], b - a)result = self.sum(y.first);t = self.merge(x[0], self.merge(y[0], y[1]));proc set_propagate[S,T](self:RBST[S,T], t:var Node[S,T], a,b:int, p:T):void =varx = self.split(t, a)y = self.split(x.second, b - a)y.first.lazy = self.h(y.first.lazy, p)t = self.merge(x.first, self.merge(self.propagate(y.first), y.second))proc set_element[S,T](self:RBST[S,T], t: var Node[S,T], k:int, x:S):void =t = self.propagate(t);if k < self.count(t.l): self.set_element(t.l, k, x)elif k == self.count(t.l): t.key = t.sum;t.sum = xelse:self.set_element(t.r, k - count(t.l) - 1, x)t = update(t)proc size[S,T](self:RBST[S,T], t:Node[S,T]):int =return self.count(t)proc empty[S,T](self:RBST[S,T], t:Node[S,T]):bool =return t == nilproc makeset[S,T](self:RBST[S,T]):Node[S,T] =return niltype OrderedMultiSet[S] = ref object of RBST[S,S]discardproc newOrderedMultiSet[S]():OrderedMultiSet[S] =return OrderedMultiSet[S](f:proc(x,y:S):S = x,M1:0)proc kthElement[S](self:OrderedMultiSet[S], t:var Node[S,S], k:int):S =if k < self.count(t.l): return self.kthElement(t.l, k)if k == self.count(t.l): return t.keyreturn self.kthElement(t.r, k - self.count(t.l) - 1)proc insertKey[S](self:OrderedMultiSet[S], t:var Node[S,S],x:S):void =self.insert(t, self.lowerBound(t, x), x)proc eraseKey[S](self:OrderedMultiSet[S], t:var Node[S,S], x:S):void =if self.count(t, x)==0: returnself.erase(t, self.lower_bound(t, x))proc count[S](self:OrderedMultiSet[S], t:Node[S,S], x:S):int =return self.upperBound(t, x) - lowerBound(t, x)proc lowerBound[S](self:OrderedMultiSet[S], t:Node[S,S], x:S):int =if t == nil: return 0if x <= t.key: return self.lowerBound(t.l, x)return self.lowerBound(t.r, x) + self.count(t.l) + 1proc upperBound[S](self:OrderedMultiSet[S], t:Node[S,S], x:S):int=if t==nil: return 0if x < t.key: return self.upperBound(t.l, x)return self.upperBound(t.r, x) + self.count(t.l) + 1varrbst = newRBST[int](proc(x,y:int):int = x + y,0)nd:Node[int,int] = rbst.build(@[1,2,3,4,5,6,7,8])proc main():void =varQ = nextInt()K = nextInt()s = newOrderedMultiSet[int]()nd:Node[int,int] = nilfor i in 0..<Q:var q = nextInt()if q==1:var v = nextInt()s.insertKey(nd,v)else:if s.count(nd) < K:echo -1else:var(l,r) = s.split(nd,K-1)(rl,rr) = s.split(r,1)echo rl.keynd = s.merge(l,rr)main()