結果

問題 No.59 鉄道の旅
コンテスト
ユーザー むらため
提出日時 2019-01-17 06:08:21
言語 Nim
(2.2.8)
コンパイル:
nim --nimcache=~ --hints:off -o:a.out -d:release cpp _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 1,928 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,374 ms
コンパイル使用メモリ 67,504 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2026-03-22 02:24:00
合計ジャッジ時間 3,464 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 41) Warning: imported and not used: 'sugar' [UnusedImport]

ソースコード

diff #
raw source code 

import sequtils,strutils,algorithm,math,sugar,macros
template get*():string = stdin.readLine().strip()
macro unpack*(arr: auto,cnt: static[int]): auto =
  let t = genSym(); result = quote do:(let `t` = `arr`;())
  for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`])
template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body)
template `max=`*(x,y:typed):void = x = max(x,y)
template `min=`*(x,y:typed):void = x = min(x,y)

type BinaryIndexedTree*[CNT:static[int],T] = object
  data: array[CNT,T]
proc `[]`*[CNT,T](bit:BinaryIndexedTree[CNT,T],i:int): T =
  if i == 0 : return bit.data[0]
  result = 0 # 000111122[2]2223333
  var index = i
  while index > 0:
    result += bit.data[index]
    index -= index and -index # 0111 -> 0110 -> 0100
proc inc*[CNT,T](bit:var BinaryIndexedTree[CNT,T],i:int,val:T) =
  var index = i
  while index < bit.data.len():
    bit.data[index] += val
    index += index and -index # 001101 -> 001110 -> 010001
proc `$`*[CNT,T](bit:BinaryIndexedTree[CNT,T]): string =
  result = "["
  for i in 0..bit.data.high: result &= $(bit[i]) & ", "
  return result[0..result.len()-2] & "]"
proc len*[CNT,T](bit:BinaryIndexedTree[CNT,T]): int = bit.data.len()

template useScan =
  proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
  proc scan(): int =
    result = 0
    var minus = false
    while true:
      var k = getchar_unlocked()
      if k == '-' : minus = true
      elif k < '0' or k > '9': break
      else: result = 10 * result + k.ord - '0'.ord
    if minus: result *= -1

# useBinaryIndexedTree()
useScan()

var cargo : BinaryIndexedTree[100_0001,int]
var last = 0
let n = scan()
let k = scan()
n.times:
  let w = scan()
  if w > 0:
    if last - cargo[w-1] >= k: continue # W以上の荷物がK個以上
    cargo.inc w, 1
    last += 1
  else:
    if cargo[-w-1] == cargo[-w] : continue # 荷物が無い
    cargo.inc -w,-1
    last -= 1
echo last
0