AT_abc457_e.Crossing Table Cloth

提高+/省选-

通过率:0%

时间限制:2.50s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN cells arranged in a horizontal row. The ii-th cell from the left (1≤i≤N)(1 \le i \le N) is called cell ii.

There are MM pieces of cloth. Laying cloth ii (1≤i≤M)(1 \le i \le M) covers cells LiL_i through RiR_i.

Answer QQ queries. For the qq-th query (1≤q≤Q)(1 \le q \le Q), integers SqS_q and TqT_q are given, so answer the following problem.

  • Determine whether it is possible to choose exactly two pieces of cloth from the MM pieces and lay them so that the following condition is satisfied.
    • Cells SqS_q through TqT_q are covered by at least one piece of cloth, and no other cells are covered by any cloth.

有 NN 个单元格从左到右水平排列。从左起第 ii 个单元格(1≤i≤N1 \le i \le N)称为单元格 ii。

有 MM 块布料。铺设第 ii 块布料(1≤i≤M1 \le i \le M)将覆盖从单元格 LiL_i 到单元格 RiR_i 的所有单元格。

回答 QQ 个查询。对于第 qq 个查询(1≤q≤Q1 \le q \le Q),给定整数 SqS_q 和 TqT_q,请回答以下问题:

  • 判断是否能从 MM 块布料中恰好选择两块并铺设,使得满足如下条件:
    • 单元格 SqS_q 到单元格 TqT_q 被至少一块布料覆盖,且除此之外的任何单元格均不被任何布料覆盖。

输入格式

The input is given from Standard Input in the following format:

NN MM
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LML_M RMR_M
QQ
S1S_1 T1T_1
S2S_2 T2T_2
⋮\vdots
SQS_Q TQT_Q

输入从标准输入中按以下格式给出:

NN MM
L1L_1 R1R_1
L2L_2 R2R_2
⋮\vdots
LML_M RMR_M
QQ
S1S_1 T1T_1
S2S_2 T2T_2
⋮\vdots
SQS_Q TQT_Q

输出格式

Output the answers for the queries, separated by newlines.

For each query, output Yes if it is possible to choose two pieces of cloth satisfying the condition, and No otherwise.

输出每个查询的答案,答案之间用换行符分隔。

对于每个查询,如果能够选择两块满足条件的布料,则输出 Yes;否则输出 No。

输入输出样例

  • 输入#1

    4 3
    1 3
    1 1
    2 4
    4
    1 4
    2 4
    1 3
    1 1

    输出#1

    Yes
    No
    Yes
    No
  • 输入#2

    7 10
    2 6
    2 5
    3 6
    1 6
    1 2
    5 6
    2 3
    3 7
    2 3
    1 2
    10
    1 2
    3 5
    1 4
    1 5
    1 5
    5 7
    1 6
    2 3
    5 7
    2 4

    输出#2

    Yes
    No
    No
    Yes
    Yes
    No
    Yes
    Yes
    No
    No

说明/提示

Sample 1 Explanation:
For the first query, the condition can be satisfied by choosing cloth 11 and cloth 33.

For the third query, the condition can be satisfied by choosing cloth 11 and cloth 22.

For the second and fourth queries, no choice of two pieces of cloth can satisfy the condition.

Constraints

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 2≤M≤2×1052 \le M \le 2 \times 10^5
  • 1≤Li≤Ri≤N1 \le L_i \le R_i \le N
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • 1≤Sq≤Tq≤N1 \le S_q \le T_q \le N
  • All input values are integers.

样例 1 解释:
对于第一个查询,可以选择布料 11 和布料 33 来满足条件。

对于第三个查询,可以选择布料 11 和布料 22 来满足条件。

对于第二个和第四个查询,不存在任何两种布料的选择能够满足条件。

约束条件

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 2≤M≤2×1052 \le M \le 2 \times 10^5
  • 1≤Li≤Ri≤N1 \le L_i \le R_i \le N
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • 1≤Sq≤Tq≤N1 \le S_q \le T_q \le N
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页