結果

問題 No.1864 Shortest Paths Counting
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:59:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 3,261 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 155,260 KB
最終ジャッジ日時 2025-03-31 17:59:52
合計ジャッジ時間 7,461 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing
    
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] = (self.tree[idx] + delta) % MOD
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res = (res + self.tree[idx]) % MOD
            idx -= idx & -idx
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    
    points = []
    for i in range(N):
        x = int(input[ptr])
        y = int(input[ptr+1])
        ptr +=2
        u = x + y
        v = x - y
        points.append( (u, v) )
    
    start = 0
    end = N-1
    
    start_u, start_v = points[start]
    end_u, end_v = points[end]
    
    delta_u = end_u - start_u
    delta_v = end_v - start_v
    
    s_u = 1 if delta_u > 0 else (-1 if delta_u <0 else 0)
    s_v = 1 if delta_v > 0 else (-1 if delta_v <0 else 0)
    
    # Filter points
    filtered = []
    for i in range(N):
        u_i, v_i = points[i]
        # Check allowed_u
        allowed_u = False
        if delta_u ==0:
            allowed_u = (u_i == start_u)
        else:
            check1 = (u_i - start_u) * s_u >=0
            check2 = (u_i - end_u) * s_u <=0
            allowed_u = check1 and check2
        
        # Check allowed_v
        allowed_v = False
        if delta_v ==0:
            allowed_v = (v_i == start_v)
        else:
            check1_v = (v_i - start_v) * s_v >=0
            check2_v = (v_i - end_v) * s_v <=0
            allowed_v = check1_v and check2_v
        
        if allowed_u and allowed_v:
            filtered.append( (u_i, v_i, i) )  # store u, v, original index
    
    # Check if start and end are in filtered
    start_in = any(p[2] == start for p in filtered)
    end_in = any(p[2] == end for p in filtered)
    if not start_in or not end_in:
        print(0)
        return
    
    # Sort the filtered points
    # Sort key: (u * s_u, v * s_v)
    sorted_points = sorted(filtered, key=lambda p: (p[0] * s_u, p[1] * s_v))
    
    # Prepare for v coordinate compression
    v_list = [p[1] for p in sorted_points]
    unique_v = list( set(v_list) )
    if s_v ==1 or s_v ==0:  # 0 is handled if delta_v is zero, but allowed_v would be same
        # sort ascending for s_v=1 (since allowed points v is increasing)
        unique_v_sorted = sorted(unique_v)
    else:
        # s_v is -1, sort descending
        unique_v_sorted = sorted(unique_v, reverse=True)
    
    # Create mapping from v to compressed index (1-based)
    v_map = {v: i+1 for i, v in enumerate(unique_v_sorted)}
    v_size = len(unique_v_sorted)
    
    # Initialize Fenwick Tree
    fenwick = FenwickTree(v_size)
    
    answer = 0
    for p in sorted_points:
        u_p, v_p, idx_p = p
        v_rank = v_map[v_p]
        if idx_p == start:
            current =1
        else:
            current = fenwick.query(v_rank)
        
        if idx_p == end:
            answer = (answer + current) % MOD
        
        fenwick.update(v_rank, current)
    
    print(answer % MOD)

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