Min Max Subarrays II
플래티넘 II의견: 0
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\).
Problem credits: Charlie Yang
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
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\).
3
2 2
1 1 2 1
1 1 2 2
2 2
1 1 2 1
1 2 2 2
4 1
2 2 4 3-1
1 2
0 3 0 0In 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.
4
2 2
1 1 2 1
2 1 2 2
3 2
1 1 2 3
2 2 3 1
5 2
1 1 2 3
1 4 5 2
4 4
1 1 4 1
1 2 3 2
2 1 2 5
2 3 4 61 2
-1
3 3 0 2 2
1 5 2 6In 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.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Platinum
평가 및 의견
Min Max Subarrays II
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Min Max Subarrays II