A50543.聊天室

普及+/提高

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

AliceAlice 近期压力颇大,渴望找网友聊聊天来舒缓情绪。 AliceAlice 共有 mm 位网友,她打算从中挑选一位进行交流。

设定一天被划分为 nn 个时刻。 AliceAlice 的网友们生活作息十分规律,第 ii 位网友从每天的时刻 lil_i 起有空聊天,到时刻 rir_i 末结束聊天状态。

在接下来的 qq 天里,AliceAlice 会在 uiu_i 时刻拿起手机开始寻找聊天对象,并在 viv_i 时刻放下手机。而且,若 AliceAlice 能与某位网友持续聊天 did_i 时长,她就能成功放松下来。那么问题来了,在这接下来的 qq 天中,AliceAlice 在哪几天能够通过与网友聊天而得以休息呢?

输入格式

第一行输入三个正整数 nnmmqq ,分别表示一天的时刻数、AliceAlice 的网友数量、接下来的天数。

接下来 mm 行,每行输入两个正整数 lil_irir_i ,表示第 ii 个网友可以聊天的起始时刻和结束时刻(包含该时刻)。

再接下来 qq 行,每行输入三个正整数 uiu_iviv_idid_i ,表示在第 ii 天,AliceAlice 拿起手机的时刻、放下手机的时刻以及她需要和网友聊天的时长。

输出格式

输出 qq 行,每行输出一个字符串 "Yes" 或 "No"。如果在第 ii 天,AliceAlice 能够找到合适的网友聊天并达到 did_i 的时长从而放松下来,就输出 "Yes";否则输出 "No"。

输入输出样例

  • 输入#1

    3 1 2
    1 2
    1 3 2
    2 3 2
    

    输出#1

    Yes
    No
    

说明/提示

数据范围

  • 1n5×1051 \leq n \leq 5\times 10^5
  • 1m5×1051 \leq m \leq 5\times 10^5
  • 1q5×1051 \leq q \leq 5\times 10^5
  • 1lirin1 \leq l_i \le r_i \leq n
  • 1uivin1 \leq u_i \le v_i \leq n
  • 1diviui+11 \leq d_i \leq v_i - u_i + 1

样例解释:
在样例一中,设定一天包含 33 个时刻,Alice拥有一位网友。这位网友每天在时刻区间 [1,2][1, 2] 处于在线状态(即从时刻 11 开始在线,到时刻 22 末结束在线)。

第一天,Alice可用于聊天的空闲时间区间为 [1,3][1, 3] ,她期望与网友的聊天时长为 22 。在此情况下,因为有个网友在时刻 11 与时刻 22 在线 。Alice能够利用时刻 11 和时刻 22 与网友进行交流,从而成功放松下来。

然而到了第二天,Alice可用于聊天的空闲时间区间变为 [2,3][2, 3] ,但她期望的聊天时长仍为 22 。 但是在此区间,只有网友 22 在时刻 22 在时刻 22 在线 ,这意味着Alice最多只能和网友聊 11 个时刻,所以在第二天,Alice无法通过与网友聊天达到期望时长,进而得不到有效的放松 。

首页