結果

問題 No.1000 Point Add and Array Add
ユーザー nadeshinonadeshino
提出日時 2020-05-19 12:49:25
言語 Nim
(2.0.2)
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 1,919 bytes
コンパイル時間 2,969 ms
コンパイル使用メモリ 66,716 KB
実行使用メモリ 21,888 KB
最終ジャッジ日時 2024-04-09 22:06:07
合計ジャッジ時間 6,809 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 126 ms
16,768 KB
testcase_17 AC 107 ms
12,672 KB
testcase_18 AC 176 ms
21,888 KB
testcase_19 AC 168 ms
20,960 KB
testcase_20 AC 151 ms
11,776 KB
testcase_21 AC 168 ms
17,536 KB
testcase_22 AC 165 ms
18,432 KB
testcase_23 AC 171 ms
17,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math, sequtils, strutils
 
let read* = iterator: string =
  while true: (for s in stdin.readLine.split: yield s)
 
template input*(T: static[typedesc]): untyped = 
  when T is int: read().parseInt
  elif T is float: read().parseFloat
  elif T is string: read()
  elif T is char: read()[0]

# -------------------------------------------------- #

type BinaryIndexedTree = object
  size: int
  data: seq[int]

proc initBinaryIndexedTree*(N: int): BinaryIndexedTree =
  result.size = N
  result.data = newSeq[int](N + 1)

proc add*(self: var BinaryIndexedTree, a: int, x: int) =
  var i = a
  while i <= self.size:
    self.data[i] += x
    i += i and -i

proc prefixSum*(self: BinaryIndexedTree, a: int): int =
  result = 0
  var i = a
  while i > 0:
    result += self.data[i]
    i -= i and -i

proc sum*(self: BinaryIndexedTree, a: int, b: int): int =
  return self.prefixSum(b) - self.prefixSum(a - 1)

proc lowerBound*(self: BinaryIndexedTree, x: int): int =
  var i, sum = 0
  var k = nextPowerOfTwo(self.size)
  while k > 0:
    if i + k <= self.size and sum + self.data[i + k] < x:
      i += k
      sum += self.data[i]
    k = k div 2
  return i + 1

proc `$`*(self: BinaryIndexedTree): string =
  result = "@[0, "
  for i in 1 .. self.size:
    result.add($self.sum(i, i) & (if i < self.size: ", " else: "]"))

# -------------------------------------------------- #

let N, Q = input(int)
var A = @[0] & newSeqWith(N, input(int))
var B = newSeqWith(N + 1, 0)
var cum = initBinaryIndexedTree(N + 1)
for _ in 1 .. Q:
  let c = input(char)
  case c
  of 'A':
    let x, y = input(int)
    let k = cum.sum(0, x)
    B[x] += k * A[x]
    cum.add(x, -k)
    cum.add(x + 1, k)
    A[x] += y
  of 'B':
    let x, y = input(int)
    cum.add(x, 1)
    cum.add(y + 1, -1)
  else: assert false
for i in 1 .. N:
  let k = cum.sum(i, i)
  B[i] += k * A[i]
  cum.add(i, -k)
  cum.add(i + 1, k)
echo B[1 .. N].join(" ")
0