A50543.聊天室
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
Alice 近期压力颇大,渴望找网友聊聊天来舒缓情绪。 Alice 共有 m 位网友,她打算从中挑选一位进行交流。
设定一天被划分为 n 个时刻。 Alice 的网友们生活作息十分规律,第 i 位网友从每天的时刻 li 起有空聊天,到时刻 ri 末结束聊天状态。
在接下来的 q 天里,Alice 会在 ui 时刻拿起手机开始寻找聊天对象,并在 vi 时刻放下手机。而且,若 Alice 能与某位网友持续聊天 di 时长,她就能成功放松下来。那么问题来了,在这接下来的 q 天中,Alice 在哪几天能够通过与网友聊天而得以休息呢?
输入格式
第一行输入三个正整数 n 、 m 、 q ,分别表示一天的时刻数、Alice 的网友数量、接下来的天数。
接下来 m 行,每行输入两个正整数 li 、 ri ,表示第 i 个网友可以聊天的起始时刻和结束时刻(包含该时刻)。
再接下来 q 行,每行输入三个正整数 ui 、 vi 、 di ,表示在第 i 天,Alice 拿起手机的时刻、放下手机的时刻以及她需要和网友聊天的时长。
输出格式
输出 q 行,每行输出一个字符串 "Yes" 或 "No"。如果在第 i 天,Alice 能够找到合适的网友聊天并达到 di 的时长从而放松下来,就输出 "Yes";否则输出 "No"。
输入输出样例
输入#1
3 1 2 1 2 1 3 2 2 3 2
输出#1
Yes No
说明/提示
数据范围
- 1≤n≤5×105
- 1≤m≤5×105
- 1≤q≤5×105
- 1≤li≤ri≤n
- 1≤ui≤vi≤n
- 1≤di≤vi−ui+1
样例解释:
在样例一中,设定一天包含 3 个时刻,Alice拥有一位网友。这位网友每天在时刻区间 [1,2] 处于在线状态(即从时刻 1 开始在线,到时刻 2 末结束在线)。
第一天,Alice可用于聊天的空闲时间区间为 [1,3] ,她期望与网友的聊天时长为 2 。在此情况下,因为有个网友在时刻 1 与时刻 2 在线 。Alice能够利用时刻 1 和时刻 2 与网友进行交流,从而成功放松下来。
然而到了第二天,Alice可用于聊天的空闲时间区间变为 [2,3] ,但她期望的聊天时长仍为 2 。 但是在此区间,只有网友 2 在时刻 2 在时刻 2 在线 ,这意味着Alice最多只能和网友聊 1 个时刻,所以在第二天,Alice无法通过与网友聊天达到期望时长,进而得不到有效的放松 。