2024年12月USACO竞赛银奖组问题二—Deforestation

Farmer John is expanding his farm! He has identified the perfect location in the Red-Black Forest, which consists of N trees (1≤N≤105  ) on a number line, with the i-th tree at position xi (−109≤xi ≤109).

Environmental protection laws restrict which trees Farmer John can cut down to make space for his farm. There are K restrictions (1≤K≤105 ) specifying that there must always be at least ti trees (1≤ti ≤N) in the line segment [li,ri]
, including the endpoints (−109≤li≤ri≤109). 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!

INPUT FORMAT (input arrives from the terminal / stdin):

Each input consists of T (1≤T≤10) independent test cases. It is guaranteed that the sums of all N and of all K within an input each do not exceed 3⋅105.

The first line of input contains T. Each test case is then formatted as follows:

The first line contains integers N and K.
The next line contains the N integers x1,…,xN.
Each of the next K lines contains three space-separated integers: li, ri and ti.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output a single line with an integer denoting the maximum number of trees Farmer John can cut down.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
4
3

For the first test case, Farmer John can cut down the first 4 trees, leaving trees at

xi = 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.

SCORING:

Input 2: N , K≤16
Inputs 3-5: N, K≤1000
Inputs 6-7:ti=1 for all i=1,…,K.
Inputs 8-11: No additional constraints.

Problem credits: Tina Wang, Jiahe Lu, Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

USACO竞赛考试网-二维码

历年学员USACO获奖战绩一览

2026赛季5位铂金级
2024-2025赛季5位铂金级
20238位铂金级

USACO 历年战绩

2026赛季战绩

  • 5位铂金级
  • 22位金级
  • 25位银级

2024–2025赛季战绩

翰林考点及辅导学生

  • 5位铂金级
  • 25位金级
  • 38位银级

2023–2024赛季战绩

  • 8位铂金级
  • 32位金级
  • 37位银级

2022–2023赛季战绩

  • 10位铂金级
  • 29位金级
  • 71位银级

篇幅有限,仅展示部分年份战绩。

在线咨询
微信咨询