結果

問題 No.1864 Shortest Paths Counting
ユーザー ChipppppChippppp
提出日時 2022-03-02 20:42:21
言語 Nim
(2.0.2)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 1,494 bytes
コンパイル時間 6,453 ms
コンパイル使用メモリ 72,408 KB
実行使用メモリ 48,428 KB
最終ジャッジ日時 2023-09-23 13:42:29
合計ジャッジ時間 10,706 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 229 ms
47,672 KB
testcase_10 AC 232 ms
47,804 KB
testcase_11 AC 233 ms
47,692 KB
testcase_12 AC 244 ms
48,220 KB
testcase_13 AC 234 ms
47,676 KB
testcase_14 AC 238 ms
47,788 KB
testcase_15 AC 248 ms
47,848 KB
testcase_16 AC 231 ms
47,848 KB
testcase_17 AC 240 ms
47,828 KB
testcase_18 AC 239 ms
47,844 KB
testcase_19 AC 234 ms
47,728 KB
testcase_20 AC 240 ms
47,712 KB
testcase_21 AC 238 ms
47,696 KB
testcase_22 AC 236 ms
47,788 KB
testcase_23 AC 232 ms
47,740 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 257 ms
48,428 KB
testcase_26 AC 201 ms
47,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sugar, system, strutils, sequtils, tables, algorithm

const MOD = 998244353

# mod 998244353のFenwickTree
type FenwickTreeMod = object
  n: int
  data: seq[int]
proc init(self: typedesc[FenwickTreeMod], n: int): FenwickTreeMod =
  return self(n: n, data: newSeq[int](n + 1))
proc add(self: var FenwickTreeMod, k, x: int): void =
  var p = k
  p.inc
  while p <= self.n:
    self.data[p] = (self.data[p] + x) mod MOD
    p += p and -p
proc sum(self: FenwickTreeMod, k: int): int =
  var
    p = k
    res = 0
  while p != 0:
    res = (res + self.data[p]) mod MOD
    p -= p and -p
  return res

# 座標圧縮
proc compress(a: seq[int]): Table[int, int] =
  var mem: Table[int, int]
  for idx, elm in a.sorted.deduplicate(isSorted = true):
    mem[elm] = idx
  return mem

# 入力
var N = stdin.readline.parseInt
var X, Y = newSeq[int](N)
for i in 0..<N:
  var a, b: int
  (a, b) = stdin.readline.split.map parseInt
  (X[i], Y[i]) = (a + b, a - b)

# 座標を反転しておく
if X[0] > X[N - 1]:
  X.applyIt(-it)
if Y[0] > Y[N - 1]:
  Y.applyIt(-it)

# y座標を圧縮
var mem = compress(Y)
Y.applyIt(mem[it])

# x, y座標が範囲内の点のみソート
var points = collect newSeq:
  for (i, j) in zip(X, Y):
    if X[0] <= i and i <= X[N - 1] and Y[0] <= j and j <= Y[N - 1]:
      (x:i, y:j)
points.sort

# DP
var ft = FenwickTreeMod.init(mem.len)
ft.add(Y[0], 1)
for i in 1..<points.len - 1:
  ft.add(points[i].y, ft.sum(points[i].y + 1))

# 出力
echo ft.sum(Y[N - 1] + 1)
0