#P3734. [Ontak2013]Miny

    ID: 591 传统题 1000ms 128MiB 尝试: 168 已通过: 27 难度: 7 上传者: 标签>CF2300提高+/省选-二分查找线段树优化建图Tarjan 强连通分量算法缩点DAG 动态规划不变量分析

[Ontak2013]Miny

题目描述

一个平面内有N个地雷,分布在X轴上。每个地雷爆炸后影响的范围是一个贺。 在这圆内的地雷也会引爆。现在告诉你每个地雷所在坐标Xi及爆炸半径Ri。请问:这些雷中任一个被引爆后一共会有多少个雷爆炸,注意爆炸是会引起连锁反应的。 1<=N<=100000 |Xi|<=10^18. 0<=Ri<=2*10^18

输入格式

输出格式

1
5
0 2
2 1
3 2
4 1
6 2
4 3 3 3 4

提示

没有写明提示

题目来源

没有写明来源