ヒント

解説

\(i\) 番目に行う操作を操作 \(i\) とします。

また、各操作について、前者の操作を左操作、後者の操作を右操作とします。

\(1\leq i\lt j\leq Q\) なるすべての整数の組 \((i,j)\) について、操作 \(i\) と操作 \(j\) の関係を考えましょう。

• \(V_i\leq V_j\) のとき: どのようにしてもよい
• \(V_i\gt V_j\) かつ \(P_i=P_j\) のとき: どのようにしても操作 \(j\) ですぬけ君が泣き出してしまうため、\(0\) が答えになる
• \(V_i\gt V_j\) かつ \(P_i\lt P_j\) のとき: 操作 \(i\) で左操作を、操作 \(j\) で右操作をしなければならない
• \(V_i\gt V_j\) かつ \(P_i\gt P_j\) のとき: 操作 \(i\) で右操作を、操作 \(j\) で左操作をしなければならない

このように各操作の向きを決めて、矛盾した場合は明らかに答えは \(0\) です。

矛盾していない場合、答えは \(1\) 以上 です。どの操作を見ても、過去の操作の後にその操作を行えるように向きを設定しているためです。向きを設定していないものはどちらの操作をしても問題ないので、そのようなものの個数を \(x\) として、\(2^x\) を \(998244353\) で割った余りが答えです。

よって、これらをそのまま実装することで \(O(Q^2)\) 時間で答えを求められます。これは十分高速なので、この問題を解くことができました。

想定解 (PyPy3)

def change(p,k):
    global kind
    if kind[p]==0:
        kind[p]=k
    elif kind[p]!=k:
        print(0)
        exit()

N,Q=map(int,input().split())
ope=[tuple(map(int,input().split())) for i in range(Q)]
kind=[0]*Q
for i in range(Q):
    for j in range(i+1,Q):
        if ope[i][1]<=ope[j][1]:
            continue
        if ope[i][0]==ope[j][0]:
            print(0)
            exit()
        elif ope[i][0]<ope[j][0]:
            change(i,-1)
            change(j,1)
        else:
            change(i,1)
            change(j,-1)
print(pow(2,kind.count(0),998244353))

Bonus!: \(N,Q\leq 2\times 10^5\) の場合でも高速に解ける方法を考えてみましょう。(実装例)