레이팅 미적용농부 존이 농장을 확장하려 한다! 그는 레드-블랙 숲에서 완벽한 위치를 찾았다. 이 숲은 수직선 위의 \(N\)(\(1 \le N \le 10^5\))그루의 나무로 이루어져 있으며, \(i\)번째 나무는 위치 \(x_i\)(\(-10^9 \le x_i \le 10^9\))에 있다.
환경 보호법은 농부 존이 농장 부지를 마련하기 위해 벨 수 있는 나무를 제한한다. \(K\)(\(1 \leq K \leq 10^5\))개의 제한이 있으며, 각 제한은 양 끝점을 포함한 선분 \([l_i, r_i]\)(\(-10^9 \le l_i \leq r_i \le 10^9\))에 항상 최소 \(t_i\)(\(1 \leq t_i \leq N\))그루의 나무가 있어야 한다는 것을 명시한다. 레드-블랙 숲이 처음에 이 제한들을 만족함이 보장된다.
농부 존은 농장을 최대한 크게 만들고 싶다. 모든 제한을 만족하면서 벨 수 있는 나무의 최대 개수를 계산하도록 도와주자!
문제 제공: Tina Wang, Jiahe Lu, Benjamin Qi
배점
- 입력 2: \(N, K \le 16\)
- 입력 3-5: \(N, K \le 1000\)
- 입력 6-7: 모든 \(i = 1, \dots, K\)에 대해 \(t_i = 1\)이다.
- 입력 8-11: 추가 제약 없음.
문제 제공: Tina Wang, Jiahe Lu, Benjamin Qi
각 입력은 \(T\)(\(1 \le T \le 10\))개의 독립적인 테스트 케이스로 이루어진다. 입력 내 모든 \(N\)의 합과 모든 \(K\)의 합이 각각 \(3 \cdot 10^5\)를 넘지 않음이 보장된다.
첫째 줄에 \(T\)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
- 첫째 줄에 정수 \(N\)과 \(K\)가 주어진다.
- 다음 줄에 \(N\)개의 정수 \(x_1, \dots, x_N\)이 주어진다.
- 다음 \(K\)개의 줄에 공백으로 구분된 세 정수 \(l_i\), \(r_i\), \(t_i\)가 각각 주어진다.
각 테스트 케이스에 대해, 농부 존이 벨 수 있는 나무의 최대 개수를 나타내는 정수를 한 줄에 출력한다.
3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 44
4
3For the first test case, Farmer John can cut down the first \(4\) trees, leaving
trees at \(x_i = 2, 6, 7\) to satisfy the restriction.
For the second test case, the additional restriction does not affect which trees
Farmer John can cut down, so he can cut down the same trees and satisfy both
restrictions.
For the third test case, Farmer John can only cut down at most \(3\) trees because
there are initially \(7\) trees but the second restriction requires him to leave
at least \(4\) trees uncut.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Silver