레이팅 미적용정수 \(N,Q\) \((1 \leq N, Q \leq 2 \cdot 10^5)\)와, 네 정수 \(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,\) 모든 \(k_i\)는 서로 다름\()\)로 표현되는 \(Q\)개의 제약 조건이 주어진다.
모든 \(1 \leq i \leq Q\)에 대해 \(t_i=1\)이면 \(\min a[l_i ... r_i]=k_i\)이고 \(t_i=2\)이면 \(\max a[l_i ... r_i]=k_i\)가 되도록, \(0\) 이상 \(10^9\) 이하의 정수 \(N\)개로 이루어진 배열 \(a\)를 구성하시오. 유효한 배열이 여러 개 있으면 아무거나 출력한다. 유효한 배열이 존재하지 않으면 \(-1\)을 출력한다.
문제 제공: Charlie Yang
채점 방식
- 입력 3-4: \(N,Q\le 100\)이고 같은 테스트 케이스 내의 모든 \(t_i\)가 같다
- 입력 5-6: 같은 테스트 케이스 내의 모든 \(t_i\)가 같다
- 입력 7-10: \(N,Q\le 100\)
- 입력 11-14: 추가 제약 조건이 없다.
문제 제공: Charlie Yang
첫째 줄에 독립적인 테스트 케이스의 수를 나타내는 정수 \(T\) (\(1 \leq T \leq 10^4\))가 주어진다.
각 테스트 케이스의 첫째 줄에 두 정수 \(N, Q\)가 주어진다.
다음 \(Q\)개의 줄 각각에 4개의 정수 \(t_i\) \(l_i\) \(r_i\) \(k_i\)가 주어진다.
모든 테스트 케이스에 대한 \(N\)의 합과 \(Q\)의 합 모두 \(2 \cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트 케이스마다, 유효한 배열이 존재하면 \(N\)개의 정수 \(a_1\dots a_N\)을 공백으로 구분하여 한 줄에 출력한다. 그렇지 않으면 \(-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