結果

問題 No.1864 Shortest Paths Counting
ユーザー ChipppppChippppp
提出日時 2022-03-02 20:34:24
言語 Nim
(2.0.2)
結果
TLE  
実行時間 -
コード長 1,314 bytes
コンパイル時間 7,876 ms
コンパイル使用メモリ 72,680 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2023-09-23 13:41:43
合計ジャッジ時間 10,702 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
8,732 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const MOD = 998244353

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.deduplicate.sorted:
    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)

var mem = compress(Y)
Y.applyIt(mem[it])

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

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