[1] Rephrasing the condition

Let us denote the \(K\) parts of the condition by Condition \(1\) to Condition \(K\).

Then, Condition \(i\) is equivalent to \((A_{P_i} \le X-1 \iff A_{Q_i} \le Y-1)\) and \((A_{P_i} \le X \iff A_{Q_i} \le Y)\). Below, assume that we have multiple conditions in the form \(A_{P_i} \le X_i \iff A_{Q_i} \le Y_i\).

[2] Constructing the optimal solution

Let us begin with \(A=(1,1,\dots,1)\).

Then, we repeat updating \(A_{Q_i}\) to \(\max(A_{Q_i},Y_i+1)\) if \(A_{P_i} > X_i\). The case \(A_{Q_i} > Y_i\) is treated similarly.

When we have done this until there is nothing to update, if all elements of \(A\) are at most \(M\), \(A\) has the smallest possible sum. Otherwise, no sequence satisfies all conditions.

One can prove this from the fact that if \(A_{P_i} > X_i\), the only way to satisfy \(A_{P_i} \le X_i \iff A_{Q_i} \le Y\) is to let \(A_{Q_i} > Y_i\).

[3] Summary

The simulation of the above process can be done in \(\mathrm{O}(N+K)\) time if implemented appropriately.

Thus, the problem can be solved in \(\mathrm{O}(N+K)\) time.