結果

問題 No.649 ここでちょっとQK!
ユーザー chaemonchaemon
提出日時 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(81, 7) Error: invalid pragma: this: self

ソースコード

diff #
プレゼンテーションモードにする

#{{{ header
import algorithm, sequtils, tables, macros, math, sets, strutils
when defined(MYDEBUG):
import header
proc 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 = false
result = ""
while true:
var c = getchar()
if int(c) > int(' '):
get = true
result.add(c)
else:
if get: break
get = false
template `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 random
var
rnd = 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) >;
#
#
type
Node[S,T] = ref object
l,r: Node[S,T]
cnt: int
key, sum: S
lazy: T
RBST[S,T] = ref object of RootObj
M1: S
OM0: T
f: proc(x,y:S):S
g: proc(x:S,y:T):S
h: proc(x,y:T):T
p: 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 t
proc count[S,T](self:RBST[S,T], t:Node):int =
if t != nil: return t.cnt
else: return 0
proc sum[S,T](self:RBST[S,T], t:Node[S,T]):S =
if t != nil: return t.sum
else: return self.M1
proc update[S,T](self:RBST[S,T], t:Node[S,T]):Node[S,T] =
t.cnt = count(t.l) + count(t.r) + 1
t.sum = self.f(self.f(sum(t.l), t.key), sum(t.r))
return t
proc 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.OM0
return update(t)
proc merge[S,T](self:RBST[S,T], l2,r2: Node[S,T]): Node[S,T] =
if l2 == nil:
return r2
elif r2 == nil:
return l2
var
l = l2
r = r2
if 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])
var
nl = 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:
return
r = self.propagate(r)
self.dump(r.l, i, v)
v[i] = r.key
i += 1
self.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 = 0
self.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 =
var
x = 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 =
var
x = 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 =
var
x = 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 = x
else:
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 == nil
proc makeset[S,T](self:RBST[S,T]):Node[S,T] =
return nil
type OrderedMultiSet[S] = ref object of RBST[S,S]
discard
proc 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.key
return 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: return
self.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 0
if x <= t.key: return self.lowerBound(t.l, x)
return self.lowerBound(t.r, x) + self.count(t.l) + 1
proc upperBound[S](self:OrderedMultiSet[S], t:Node[S,S], x:S):int=
if t==nil: return 0
if x < t.key: return self.upperBound(t.l, x)
return self.upperBound(t.r, x) + self.count(t.l) + 1
var
rbst = 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 =
var
Q = nextInt()
K = nextInt()
s = newOrderedMultiSet[int]()
nd:Node[int,int] = nil
for i in 0..<Q:
var q = nextInt()
if q==1:
var v = nextInt()
s.insertKey(nd,v)
else:
if s.count(nd) < K:
echo -1
else:
var
(l,r) = s.split(nd,K-1)
(rl,rr) = s.split(r,1)
echo rl.key
nd = s.merge(l,rr)
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0