結果

問題 No.3748 Three Pruning Order
コンテスト
ユーザー Naru820
提出日時 2026-09-16 20:57:35
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 804 ms / 2,000 ms
+ 281µs
コード長 3,217 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 70 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 126,720 KB
最終ジャッジ日時 2026-09-25 20:53:56
合計ジャッジ時間 20,196 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

input = sys.stdin.buffer.readline


class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, p, x):
        p += 1
        while p <= self.n:
            self.data[p] += x
            p += p & -p

    def sum_prefix(self, r):
        # sum [0, r)
        s = 0
        while r > 0:
            s += self.data[r]
            r -= r & -r
        return s

    def sum(self, l, r):
        # sum [l, r)
        return self.sum_prefix(r) - self.sum_prefix(l)


def solve(n, m, p, q, r, posq, posr, ordq, ordr):
    bit = FenwickTree(n)
    a = [0] * n

    def cdq(le, ri):
        if le == ri:
            return

        mid = (le + ri) // 2
        cdq(le, mid)
        cdq(mid + 1, ri)

        left = list(range(le, mid + 1))
        right = list(range(mid + 1, ri + 1))

        left.sort(key=lambda x: ordq[x], reverse=True)
        right.sort(key=lambda x: ordq[x], reverse=True)

        j = 0

        for v in left:
            while j < len(right) and ordq[right[j]] > ordq[v]:
                bit.add(ordr[right[j]], 1)
                j += 1

            a[v] += bit.sum(ordr[v] + 1, n)

        for i in range(j):
            bit.add(ordr[right[i]], -1)

    e = []
    use = [0] * n

    # 元コード:
    # for(int i = 0; i < n; i++){
    #     p[i] = i;
    #     q[ordq[i]] = i;
    # }
    for i in range(n):
        p[i] = i
        q[ordq[i]] = i

    def add_path(order, pos):
        s = []
        mx = -1

        for i in range(n - 1, -1, -1):
            v = order[i]

            if pos[v] > mx:
                mx = pos[v]
                s.append(v)

        s.reverse()

        for v in s:
            use[v] = 1

        for i in range(len(s) - 1):
            x = s[i]
            y = s[i + 1]

            if x > y:
                x, y = y, x

            e.append((x, y))

    add_path(p, ordq)
    add_path(p, ordr)
    add_path(q, ordr)

    e.sort()

    # C++ の
    # sort(e.begin(), e.end());
    # e.erase(unique(e.begin(), e.end()), e.end());
    # に対応
    if e:
        unique_e = [e[0]]
        for i in range(1, len(e)):
            if e[i] != e[i - 1]:
                unique_e.append(e[i])
        e = unique_e

    vcnt = sum(use)

    if len(e) != vcnt - 1:
        return 0

    cdq(0, n - 1)

    ans = 1

    for i in range(n):
        ans = ans * max(1, a[i]) % m

    return ans


def main():
    t = int(input())

    out = []

    for _ in range(t):
        n, m = map(int, input().split())

        p = [x - 1 for x in map(int, input().split())]

        q = [x - 1 for x in map(int, input().split())]
        posq = [0] * n
        for i in range(n):
            posq[q[i]] = i

        r = [x - 1 for x in map(int, input().split())]
        posr = [0] * n
        for i in range(n):
            posr[r[i]] = i

        ordq = [0] * n
        ordr = [0] * n

        for i in range(n):
            ordq[i] = posq[p[i]]
            ordr[i] = posr[p[i]]

        ans = solve(
            n, m,
            p, q, r,
            posq, posr,
            ordq, ordr
        )

        out.append(str(ans))

    sys.stdout.write("\n".join(out))


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