結果

問題 No.1000 Point Add and Array Add
ユーザー nadeshino
提出日時 2020-05-19 12:49:25
言語 Nim
(2.2.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 1,919 bytes
コンパイル時間 4,271 ms
コンパイル使用メモリ 65,956 KB
実行使用メモリ 21,900 KB
最終ジャッジ日時 2024-10-01 22:38:49
合計ジャッジ時間 9,016 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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