网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
线段覆盖
成绩 | 0 | 开启时间 | 2013年01月22日 星期二 13:35 |
折扣 | 0.8 | 折扣时间 | 2013年01月22日 星期二 13:35 |
允许迟交 | 是 | 关闭时间 | 2013年01月22日 星期二 13:35 |
输入文件 | xdfg.in | 输出文件 | xdfg.out |
【问题描述】
有一根长度为 L 的白色条状物。有两种操作:
- 用一条长度为 T 的黑布盖住条状物的 [a, a+T] 这个区间 (0<=a, T<=L) 。
- 把某条黑布拿走。
输入 L 和 n 次操作,要你输出每次操作之后:
- 条状物上有多少个黑区间。
- 条状物上黑区间的总长度。
【输入格式】
输入文件第一行两个整数L(1<=L<=200000), n(1<=n<=200000)
以下有n行,第2--n+1行每行有3个整数m,a,T,m表示操作类型,1表示放入黑布,2表示拿走黑布,a,T表示黑布在L上的起始位置与长度,拿走的黑布保证是原来已经存在的.
【输出格式】
输出有n行,每行两个整数x,y,x表示L上的黑区间个数,y表示黑区间的总长度.
【输入输出样例】
输入:
20 4
1 5 3
1 7 2
2 5 3
1 16 3
输出:
1 3
1 4
1 2
2 5