#339579 (Nim) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	ikd
提出日時	2019-04-18 12:40:23
言語	Nim (2.0.2)
結果	AC
実行時間	505 ms / 2,000 ms
コード長	3,150 bytes
コンパイル時間	3,200 ms
コンパイル使用メモリ	67,808 KB
実行使用メモリ	14,596 KB
最終ジャッジ日時	2023-09-14 16:02:13
合計ジャッジ時間	24,286 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	7 ms 4,380 KB
testcase_06	AC	8 ms 4,380 KB
testcase_07	AC	9 ms 4,380 KB
testcase_08	AC	4 ms 4,380 KB
testcase_09	AC	3 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	5 ms 4,380 KB
testcase_12	AC	3 ms 4,376 KB
testcase_13	AC	7 ms 4,380 KB
testcase_14	AC	4 ms 4,380 KB
testcase_15	AC	416 ms 12,848 KB
testcase_16	AC	410 ms 12,984 KB
testcase_17	AC	453 ms 12,992 KB
testcase_18	AC	450 ms 12,864 KB
testcase_19	AC	307 ms 13,056 KB
testcase_20	AC	437 ms 12,852 KB
testcase_21	AC	505 ms 13,260 KB
testcase_22	AC	446 ms 13,084 KB
testcase_23	AC	442 ms 13,040 KB
testcase_24	AC	402 ms 12,828 KB
testcase_25	AC	4 ms 4,380 KB
testcase_26	AC	4 ms 4,376 KB
testcase_27	AC	4 ms 4,376 KB
testcase_28	AC	3 ms 4,376 KB
testcase_29	AC	4 ms 4,376 KB
testcase_30	AC	3 ms 4,380 KB
testcase_31	AC	4 ms 4,380 KB
testcase_32	AC	3 ms 4,380 KB
testcase_33	AC	4 ms 4,376 KB
testcase_34	AC	4 ms 4,376 KB
testcase_35	AC	3 ms 4,376 KB
testcase_36	AC	3 ms 4,376 KB
testcase_37	AC	3 ms 4,376 KB
testcase_38	AC	4 ms 4,380 KB
testcase_39	AC	4 ms 4,384 KB
testcase_40	AC	4 ms 4,380 KB
testcase_41	AC	4 ms 4,376 KB
testcase_42	AC	3 ms 4,380 KB
testcase_43	AC	3 ms 4,380 KB
testcase_44	AC	4 ms 4,376 KB
testcase_45	AC	423 ms 14,508 KB
testcase_46	AC	408 ms 12,900 KB
testcase_47	AC	419 ms 13,092 KB
testcase_48	AC	377 ms 12,956 KB
testcase_49	AC	372 ms 13,008 KB
testcase_50	AC	383 ms 13,144 KB
testcase_51	AC	444 ms 12,804 KB
testcase_52	AC	377 ms 12,884 KB
testcase_53	AC	410 ms 13,068 KB
testcase_54	AC	433 ms 12,804 KB
testcase_55	AC	462 ms 12,884 KB
testcase_56	AC	439 ms 13,040 KB
testcase_57	AC	397 ms 12,844 KB
testcase_58	AC	411 ms 13,184 KB
testcase_59	AC	424 ms 14,568 KB
testcase_60	AC	404 ms 14,468 KB
testcase_61	AC	397 ms 13,452 KB
testcase_62	AC	387 ms 12,896 KB
testcase_63	AC	465 ms 14,484 KB
testcase_64	AC	425 ms 13,496 KB
testcase_65	AC	63 ms 12,764 KB
testcase_66	AC	66 ms 12,608 KB
testcase_67	AC	213 ms 12,920 KB
testcase_68	AC	208 ms 12,472 KB
testcase_69	AC	252 ms 12,572 KB
testcase_70	AC	221 ms 14,380 KB
testcase_71	AC	207 ms 12,740 KB
testcase_72	AC	189 ms 12,732 KB
testcase_73	AC	178 ms 12,844 KB
testcase_74	AC	243 ms 12,348 KB
testcase_75	AC	256 ms 12,764 KB
testcase_76	AC	252 ms 12,404 KB
testcase_77	AC	224 ms 12,868 KB
testcase_78	AC	244 ms 13,476 KB
testcase_79	AC	346 ms 14,288 KB
testcase_80	AC	297 ms 12,356 KB
testcase_81	AC	321 ms 12,800 KB
testcase_82	AC	298 ms 12,400 KB
testcase_83	AC	230 ms 14,596 KB
testcase_84	AC	278 ms 13,460 KB
testcase_85	AC	89 ms 13,696 KB
testcase_86	AC	97 ms 12,864 KB
testcase_87	AC	212 ms 12,800 KB
testcase_88	AC	205 ms 12,860 KB
testcase_89	AC	2 ms 4,380 KB
testcase_90	AC	2 ms 4,380 KB
testcase_91	AC	2 ms 4,380 KB

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

コンパイルメッセージ

/home/judge/data/code/Main.nim(1, 28) Warning: use `std/random` instead; mersenne is deprecated [Deprecated]

ソースコード

raw source code

import strutils, sequtils, mersenne

var mt = newMersenneTwister(0)

type Node = ref object
  val: int64
  priority: int
  size: int
  sum: int64
  left, right: Node

proc newNode(val: int64): Node =
  let node = new Node
  node.val = val
  node.priority = mt.getNum().int
  node.size = 1
  node.sum = val
  return node

type Pair = Node

proc makePair(left, right: Node): Pair =
  let pair = new Pair
  pair.left = left
  pair.right = right
  return pair

proc size(root: Node): int =
  return if root == nil: 0 else: root.size
proc sum(root: Node): int64 =
  return if root == nil: 0.int64 else: root.sum

proc update(node: Node): Node =
  node.size = 1 + size(node.left) + size(node.right)
  node.sum = node.val + sum(node.left) + sum(node.right)
  return node

# max(left) <= min(right) じゃないとダメ?
proc merge(left, right: Node): Node =
  if left == nil:
    return right
  elif right == nil:
    return left
  if left.priority > right.priority:
    left.right = merge(left.right, right)
    return update(left)
  else:
    right.left = merge(left, right.left)
    return update(right)

# k 個と size(root)-k 個に分ける
proc split(root: Node, k: int): Pair =
  if root == nil:
    return makePair(root, root)
  if k <= size(root.left):
    let pair = split(root.left, k)
    root.left = pair.right
    return makePair(pair.left, update(root))
  else:
    let pair = split(root.right, k - size(root.left) - 1)
    root.right = pair.left
    return makePair(update(root), pair.right)

proc countLess(root: Node, x: int64): int =
  if root == nil:
    return 0
  if root.val < x:
    return size(root.left) + 1 + countLess(root.right, x)
  else:
    return countLess(root.left, x) # root.val==x の分はカウントしない

proc insert(root: Node, x: int64): Node =
  let
    k = root.countLess(x)
    pair = split(root, k) # pair.left には x 未満しかない
  return merge(merge(pair.left, newNode(x)), pair.right)

proc erase(root: Node, x: int64): Node =
  let
    k = root.countLess(x)
    pair = split(root, k)
  if pair.right != nil:
    let pp = split(pair.right, 1) # pp.left は x のみ
    return merge(pair.left, pp.right)
  else: # x が存在しない
    return merge(pair.left, pair.right)

proc getKth(root: Node, k: int): Node =
  if root == nil or size(root) < k:
    return nil
  if size(root.left) + 1 == k:
    return root
  elif size(root.left) >= k:
    return getKth(root.left, k)
  else:
    return getKth(root.right, k - size(root.left) - 1)

proc main() =
  let
    nk = stdin.readLine.strip.split.map(parseInt)
    (n, k) = (nk[0], nk[1])
    a = stdin.readLine.strip.split.map(parseBiggestInt)

  var
    root: Node = nil
    ans = int64.high
  for i in 0..<n:
    root = root.insert(a[i])
    if i >= k:
      root = root.erase(a[i - k])
    if i + 1 >= k:
      let
        kth = root.getKth((k + 1) div 2)
        pair = root.split((k + 1) div 2)
      var cost: int64 = 0
      cost += kth.val * size(pair.left) - sum(pair.left)
      cost += sum(pair.right) - kth.val * size(pair.right)
      if cost < ans:
        ans = cost
      root = merge(pair.left, pair.right)
  echo ans

main()

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード