华师一附中OI组

标题: 找最长线段离散化+线段树 [打印本页]

作者: admin 时间: 2018-5-13 01:04
标题: 找最长线段离散化+线段树
【题目描述】先是在数轴区间 0 到10^9 (10的9次方）之间画上了白色。然后，这个区间的某一些部分又画上了黑色。然后某一些部分又画上白色，等等。请你找出经历M(1 <= M <= 5000)次重着色后，最长的白色区间。
【输入格式】首行位N,以下N行位重着色的信息，每一行格式如下：
ai bi ci 这里 ai ，bi 都是整数, ci 为字符'b' 或'w'，用空格隔开。
这三个参数描述：从ai到bi,着颜色ci, ('w'表示白，'b'表示黑），可以认为0 < ai <= bi < 10^9
【输出格式】输出x，y (x < y)，之间用空格隔开，表示最长的白色区间。假如有多个答案，输出x最小的那个
Sample Input
4
1 999999997 b
40 300 w
300 634 w
43 47 b
Sample Output
47 634

欢迎光临华师一附中OI组 (http://hsyit.cn/)