#362002 (Nim) No.649 ここでちょっとQK！

提出ソース

結果

問題	No.649 ここでちょっとQK！
ユーザー	chaemon
提出日時	2019-07-26 03:21:06
言語	Nim (2.0.2)
結果	AC
実行時間	935 ms / 3,000 ms
コード長	7,835 bytes
コンパイル時間	6,122 ms
コンパイル使用メモリ	75,628 KB
実行使用メモリ	16,160 KB
最終ジャッジ日時	2023-09-15 00:11:58
合計ジャッジ時間	19,724 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	276 ms 4,376 KB
testcase_04	AC	334 ms 16,132 KB
testcase_05	AC	334 ms 16,048 KB
testcase_06	AC	320 ms 16,160 KB
testcase_07	AC	2 ms 4,384 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	403 ms 8,436 KB
testcase_13	AC	399 ms 8,328 KB
testcase_14	AC	389 ms 8,304 KB
testcase_15	AC	415 ms 8,396 KB
testcase_16	AC	404 ms 8,964 KB
testcase_17	AC	458 ms 9,364 KB
testcase_18	AC	497 ms 9,912 KB
testcase_19	AC	551 ms 10,232 KB
testcase_20	AC	604 ms 10,932 KB
testcase_21	AC	656 ms 11,360 KB
testcase_22	AC	719 ms 12,028 KB
testcase_23	AC	774 ms 12,496 KB
testcase_24	AC	831 ms 12,976 KB
testcase_25	AC	884 ms 13,388 KB
testcase_26	AC	935 ms 13,868 KB
testcase_27	AC	4 ms 4,376 KB
testcase_28	AC	4 ms 4,376 KB
testcase_29	AC	4 ms 4,380 KB
testcase_30	AC	399 ms 8,464 KB
testcase_31	AC	397 ms 8,836 KB
testcase_32	AC	2 ms 4,380 KB
testcase_33	AC	2 ms 4,380 KB
testcase_34	AC	2 ms 4,380 KB
testcase_35	AC	2 ms 4,380 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

/home/judge/data/code/Main.nim(81, 1) Warning: '.this' pragma is deprecated [Deprecated]

ソースコード

raw source code

#{{{ 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()

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード