結果

問題 No.1864 Shortest Paths Counting
ユーザー ChipppppChippppp
提出日時 2022-03-02 20:42:21
言語 Nim
(2.0.2)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,494 bytes
コンパイル時間 1,634 ms
コンパイル使用メモリ 70,884 KB
最終ジャッジ日時 2024-07-16 13:19:39
合計ジャッジ時間 2,670 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
/home/judge/data/code/Main.nim(38, 32) Error: type mismatch: got 'seq[int]' for 'map(split(readLine(stdin), {' ', '\t', '\v', '\r', '\n', '\f'}, -1), parseInt)' but expected 'tuple'

ソースコード

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