結果
問題 |
No.1864 Shortest Paths Counting
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()