結果

問題 No.1864 Shortest Paths Counting
ユーザー qwewe
提出日時 2025-04-24 12:27:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 588 ms / 2,000 ms
コード長 1,902 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 152,440 KB
最終ジャッジ日時 2025-04-24 12:29:35
合計ジャッジ時間 7,172 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # Using 1-based indexing

    def update(self, idx, delta):
        idx += 1  # Convert to 1-based
        while idx <= self.n:
            self.tree[idx] = (self.tree[idx] + delta) % MOD
            idx += idx & -idx

    def query(self, idx):
        idx += 1  # Convert to 1-based
        res = 0
        while idx > 0:
            res = (res + self.tree[idx]) % MOD
            idx -= idx & -idx
        return res

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    points = []
    for _ in range(N):
        x = int(data[idx])
        y = int(data[idx+1])
        points.append((x, y))
        idx += 2

    s_x, s_y = points[0]
    t_x, t_y = points[-1]

    s_u = s_x + s_y
    s_v = s_x - s_y
    t_u = t_x + t_y
    t_v = t_x - t_y

    valid_points = []
    for i in range(N):
        x, y = points[i]
        u = x + y
        v = x - y
        if (min(s_u, t_u) <= u <= max(s_u, t_u)) and (min(s_v, t_v) <= v <= max(s_v, t_v)):
            valid_points.append((u, v, i))

    u_inc = s_u <= t_u
    v_inc = s_v <= t_v

    valid_points.sort(key=lambda p: (p[0] if u_inc else -p[0], p[1] if v_inc else -p[1]))

    vs = [p[1] for p in valid_points]
    unique_vs = list(sorted(set(vs), reverse=not v_inc))

    v_to_rank = {v: i for i, v in enumerate(unique_vs)}
    fen_size = len(unique_vs)

    ft = FenwickTree(fen_size)
    ans = 0

    for p in valid_points:
        u, v, idx_p = p
        current_v_rank = v_to_rank[v]

        if idx_p == 0:
            dp = 1
        else:
            dp = ft.query(current_v_rank)

        if idx_p == N - 1:
            ans = dp % MOD

        ft.update(current_v_rank, dp)

    print(ans % MOD)

if __name__ == "__main__":
    main()
0