Submission #1366702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1366702		makon	Dubai Chewy Cookie (KAISTRUN26SPRING_C)	Pypy 3	100 / 100	177 ms	176760 KiB

Main

import sys
input = sys.stdin.readline

MOD = 998244353

def build(arr):
    dp = [1]
    for p in arr:
        q = (1 - p) % MOD
        ndp = [0] * (len(dp) + 1)

        for i, v in enumerate(dp):
            ndp[i] = (ndp[i] + v * q) % MOD
            ndp[i + 1] = (ndp[i + 1] + v * p) % MOD

        dp = ndp

    return dp

def main():
    N, M, Q = map(int, input().split())
    P = [0] + list(map(int, input().split()))

    a = [False] * (N + 1)
    b = [False] * (N + 1)

    a[1] = True
    b[2] = True

    for _ in range(M):
        u, v = map(int, input().split())

        if u == 1:
            a[v] = True
        elif v == 1:
            a[u] = True

        if u == 2:
            b[v] = True
        elif v == 2:
            b[u] = True

    only_a = []
    only_b = []
    both = []

    for i in range(1, N + 1):
        if a[i] and b[i]:
            both.append(P[i])
        elif a[i]:
            only_a.append(P[i])
        elif b[i]:
            only_b.append(P[i])

    da = build(only_a)
    db = build(only_b)
    dc = build(both)

    la = len(da)
    lb = len(db)
    lc = len(dc)

    out = []

    for _ in range(Q):
        S, T = map(int, input().split())

        l = max(0, S - la + 1, T - lb + 1)
        r = min(S, T, lc - 1)

        if l > r:
            out.append("0")
            continue

        ans = 0
        for z in range(l, r + 1):
            ans += dc[z] * da[S - z] % MOD * db[T - z]

        out.append(str(ans % MOD))

    print('\n'.join(out))

if __name__ == "__main__": main()

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 39%)

=======

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40