#P12845. [蓝桥杯 2025 国 A] 连锁反应【数据强度待检验】

    ID: 12621 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>图论贪心线段树2025图论建模强连通分量蓝桥杯国赛

[蓝桥杯 2025 国 A] 连锁反应【数据强度待检验】

题目背景

数据强度可能较弱,可能会不定期更新。

题目描述

小蓝在数轴上放置了 nn 枚炸弹,第 ii 枚炸弹的位置为 pip_i,其爆炸范围为 [pili,pi+ri][p_i - l_i, p_i + r_i]。当一枚炸弹爆炸时,其范围内的所有其他未爆炸的炸弹均会被引爆。小蓝希望知道至少需要主动引爆多少枚炸弹,才能使得所有炸弹都爆炸。

输入格式

输入的第一行包含一个正整数 nn

接下来 nn 行,每行包含三个整数 pi,li,rip_i, l_i, r_i,相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

5
3 1 1
1 0 2
6 2 1
9 4 2
10 1 1

2

提示

【样例说明】

主动引爆炸弹 2,42, 4,即可引爆所有炸弹。

【评测用例规模与约定】

对于 20% 的评测用例,1n20001 \leq n \leq 2000

对于另外 20% 的评测用例,li=0l_i = 0

对于所有评测用例,1n2000001 \leq n \leq 2000000pi,li,ri1050 \leq p_i, l_i, r_i \leq 10^5