It suffices to brute force all possible arrays, where we can check if the array violates at most $1$ requirement in $\mathcal{O}(N^2)$ time.

$\mathcal{O}(N^{N+2})$

We observe that the constructed array must always be non-decreasing. To see this, suppose this wasn't the case and so there exists two indices $i,j$ such that $x_i>x_j$. This implies that $b_i,c_j>0$. However since $b_i=c_j=0$, this would require at least $2$ modifications which is not allowed.

We also observe that since at most one modification can be made, the constructed array must either satisfy all $a_i$ or satisfy all $d_i$. Hence, we can build $2$ possible arrays, where the first one satisfies all $a_i$ and the second one satisfies all $d_i$. For the former, we construct the array from left to right. At each index $i$, there are two possibilities:

• Case 1: $a_i=a_{i-1}$
  This means the current element must be equal to the previous element.
• Case 2: $a_i\ne a_{i-1}$
  Observe that for a solution to exist, $a_i$ must equal $i-1$, since the preceeding elements must be less than $x_i$. We set the value of $x_i$ to be the next smallest value.

After constructing the first array, we then have to check if it violates at most one $d_i$

We build the second array using all $d_i$ in a similar manner. If both arrays can be built, we pick the lexicographically smaller one.

$\mathcal{O}(N)$

We can extend the solution in subtask 2 by recognizing that $a_i+b_i$ and $c_i+d_i$ gives the rank of the $i^{\text{th}}$ element in ascending and descending order respectively. Using $a_i+b_i$ as an example, notice if we process elements in increasing order of $a_i+b_i$, we see that the values in the constructed array are uniquely determined based on whether or not the current and previous value of $a_i+b_i$ are equal.

Once both arrays are constructed, we can check if they satisfy all the requirements in $\mathcal{O}(N^2)$ time.

For full marks, we can optimize checking if an array satisfies all requirements by using a BIT.

$\mathcal{O}(N\log N)$