P15581 [USACO26FEB] Min Max Subarrays II P

You are given integers $N,Q$ $(1 \leq N, Q \leq 2 \cdot 10^5)$ and $Q$ constraints represented by four integers $t_i,l_i,r_i,k_i$ $(1 \leq t_i \leq 2, 1 \leq l_i \leq r_i \leq N, 0 \leq k_i \leq 10^9,$ all $k_i$ are distinct$).$ Construct an array $a$ consisting of $N$ integers between $0$ and $10^9$ such that for all $1 \leq i \leq Q$, $\min a[l_i ... r_i]=k_i$ if $t_i=1$ and $\max a[l_i ... r_i]=k_i$ if $t_i=2$. If multiple valid arrays exist, print any. If no valid array exists, print $-1$.

The first line contains an integer $T$ ($1 \leq T \leq 10^4$) representing the number of independent test cases. For each test case, the first line contains two integers $N, Q$. The next $Q$ lines each contain 4 integers $t_i$ $l_i$ $r_i$ $k_i$. It is guaranteed that neither the sum of $N$ nor the sum of $Q$ over all test cases exceed $2 \cdot 10^5$.

For each test case, if a valid array exists, output $N$ space-separated integers $a_1\dots a_N$ on a new line. Otherwise, print $-1$.

### Sample 1 Explanation In the first test case, the answer is $-1$ because the minimum value of the array cannot be both $1$ and $2$ at the same time. In the second test case, $a[1 ... 2]$ has a minimum of $1$ at $a[1]$ in the sample output, satisfying the first constraint. Since $a[2] = 2$, the second constraint is also satisfied. In the third test case, there are multiple solutions. For instance, the array $[4, 3, 2, 1]$ would also be accepted. ### Sample 2 Explanation In the second test case, the array $[3, 5, 1]$ satisfies the first constraint but not the second constraint. Contrarily, the array $[3, 1, 1]$ satisfies the second constraint but not the first constraint. It can be proven that no array can satisfy both constraints at the same time, hence the answer is $-1$. For all other test cases, it can be proven that the constructed array satisfies all $Q$ constraints. ### SCORING: - Inputs 3-4: $N,Q\le 100$ and all $t_i$ within the same test case are equal - Inputs 5-6: all $t_i$ within the same test case are equal - Inputs 7-10: $N,Q\le 100$ - Inputs 11-14: No additional constraints. Problem credits: Charlie Yang