#PU1447. USACO 2024 December Contest, Silver — Problem 2. Deforestation
USACO 2024 December Contest, Silver — Problem 2. Deforestation
USACO 2024 December Contest, Silver — Problem 2. Deforestation
题目描述
Farmer John is expanding his farm! He has identified the perfect location in the Red-Black Forest, which consists of trees () on a number line, with the -th tree at position (). Environmental protection laws restrict which trees Farmer John can cut down to make space for his farm. There are restrictions () specifying that there must always be at least trees () in the line segment , including the endpoints (). It is guaranteed that the Red-Black Forest initially satisfies these restrictions. Farmer John wants to make his farm as big as possible. Please help him compute the maximum number of trees he can cut down while still satisfying all the restrictions!
输入格式
Each input consists of () independent test cases. It is guaranteed that the sums of all and of all within an input each do not exceed . The first line of input contains . Each test case is then formatted as follows: The first line contains integers and . The next line contains the integers . Each of the next lines contains three space-separated integers: , and .
输出格式
For each test case, output a single line with an integer denoting the maximum number of trees Farmer John can cut down.
数据范围
(见题面原文)
样例
样例 1
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 4
4
4
3
For 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.