結果

問題 No.1864 Shortest Paths Counting
ユーザー LyricalMaestroLyricalMaestro
提出日時 2024-09-08 16:33:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 409 ms / 2,000 ms
コード長 3,259 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 158,644 KB
最終ジャッジ日時 2024-09-08 16:33:51
合計ジャッジ時間 8,837 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
52,916 KB
testcase_01 AC 38 ms
53,400 KB
testcase_02 AC 40 ms
52,620 KB
testcase_03 AC 36 ms
53,628 KB
testcase_04 AC 38 ms
53,612 KB
testcase_05 AC 37 ms
54,596 KB
testcase_06 AC 35 ms
53,980 KB
testcase_07 AC 37 ms
53,500 KB
testcase_08 AC 36 ms
53,072 KB
testcase_09 AC 274 ms
118,156 KB
testcase_10 AC 285 ms
118,284 KB
testcase_11 AC 260 ms
118,148 KB
testcase_12 AC 409 ms
135,936 KB
testcase_13 AC 277 ms
118,272 KB
testcase_14 AC 300 ms
118,152 KB
testcase_15 AC 339 ms
121,516 KB
testcase_16 AC 274 ms
118,024 KB
testcase_17 AC 318 ms
119,556 KB
testcase_18 AC 305 ms
118,152 KB
testcase_19 AC 290 ms
118,028 KB
testcase_20 AC 336 ms
125,768 KB
testcase_21 AC 254 ms
118,028 KB
testcase_22 AC 303 ms
118,024 KB
testcase_23 AC 295 ms
118,400 KB
testcase_24 AC 38 ms
52,764 KB
testcase_25 AC 398 ms
158,644 KB
testcase_26 AC 205 ms
106,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1864

MOD = 998244353

class SegmentTree:
    """
    非再帰版セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    """

    def __init__(self, init_array):
        n = 1
        while n < len(init_array):
            n *= 2
        
        self.size = n
        self.array = [0] * (2 * self.size)
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
        
        end_index = self.size
        start_index = end_index // 2
        while start_index >= 1:
            for i in range(start_index, end_index):
                self.array[i] = self.array[2 * i] + self.array[2 * i + 1]
                self.array[i] %= MOD
            end_index = start_index
            start_index = end_index // 2

    def add(self, x, a):
        index = self.size + x
        self.array[index] += a
        self.array[index] %= MOD
        while index > 1:
            index //= 2
            self.array[index] = self.array[2 * index] + self.array[2 * index + 1]
            self.array[index] %= MOD

    def get_sum(self, l, r):
        L = self.size + l; R = self.size + r

        # 2. 区間[l, r)の最大値を求める
        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s += self.array[R]
                s %= MOD
            if L & 1:
                s += self.array[L]
                s %= MOD
                L += 1                
            L >>= 1; R >>= 1
        return s


def main():
    N = int(input())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    # チェビシェフ変換 -> マンハッタン距離 * 2　の世界で考える
    uv = []
    for x, y in xy:
        u = x + y
        v = x - y
        uv.append([u, v])
    
    # u0 < uN, v0 < vNの世界で考えても問題ないように標準化する
    if uv[0][0] > uv[-1][0]:
        for i in range(N):
            uv[i][0] *= -1
    if uv[0][1] > uv[-1][1]:
        for i in range(N):
            uv[i][1] *= -1
    
    # u0 <= uN, v0 <= vNの中にいる点だけ取り出す
    uv2 = []
    for u, v in uv:
        if uv[0][0] <= u <= uv[-1][0] and uv[0][1] <= v <= uv[-1][1]:
            uv2.append((u, v))

    # uベースでまとめる
    u_map = {}
    for u, v in uv2:
        if u not in u_map:
            u_map[u] = []
        u_map[u].append(v)

    # vベースでの座標圧縮
    v_set = set()
    for _, v in uv2:
        v_set.add(v)
    v_list = list(v_set)
    v_list.sort()
    v_map = {}
    for i, v in enumerate(v_list):
        v_map[v] = i
    v_max = len(v_list)
    
    # 平面捜査による解法で実施
    seg_tree = SegmentTree([0] * v_max)
    u_array = [(u, v_array) for u, v_array in u_map.items()]
    u_array.sort(key=lambda x : x[0])
    ans = -1
    for u, v_array in u_array:
        v_array.sort()
        for v in v_array:
            if (u, v) == uv2[0]:
                seg_tree.add(0, 1)
            else:
                x = seg_tree.get_sum(0, v_map[v] + 1)
                ans = x
                seg_tree.add(v_map[v], x)
        
    print(ans)


    





    



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