Hints

Solution

Let’s denote the \(i\)-th operation as operation \(i\).

For each operation, we will refer to the former choice as the left operation and the latter choice as the right operation.

Consider the relationship between operations \(i\) and \(j\) for all integer pairs \((i, j)\) such that \(1 \leq i < j \leq Q\).

• When \(V_i \leq V_j\): Any choice is fine.
• When \(V_i > V_j\) and \(P_i = P_j\): No matter what, Snuke will cry during operation \(j\), so the answer is \(0\).
• When \(V_i > V_j\) and \(P_i < P_j\): Operation \(i\) must be a left operation, and operation \(j\) must be a right operation.
• When \(V_i > V_j\) and \(P_i > P_j\): Operation \(i\) must be a right operation, and operation \(j\) must be a left operation.

After determining the direction of each operation in this way, if there is a contradiction, it is clear that the answer is \(0\).

If there is no contradiction, the answer is at least \(1\). This is because, for any operation, the direction is set so that it can be performed after the previous operations. For those operations whose direction is not set, either choice is fine, so let \(x\) be the number of such operations, and the answer is \(2^x\) modulo \(998244353\).

Therefore, by implementing this directly, we can find the answer in \(O(Q^2)\) time. This is fast enough to solve this problem.

Judge’s Solution (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!: Consider how to solve this problem quickly even when \(N, Q \leq 2 \times 10^5\). (Sample Implementation)