AT_abc457_e.Crossing Table Cloth
提高+/省选-
通过率:0%
时间限制:2.50s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N cells arranged in a horizontal row. The i-th cell from the left (1≤i≤N) is called cell i.
There are M pieces of cloth. Laying cloth i (1≤i≤M) covers cells Li through Ri.
Answer Q queries. For the q-th query (1≤q≤Q), integers Sq and Tq are given, so answer the following problem.
- Determine whether it is possible to choose exactly two pieces of cloth from the M pieces and lay them so that the following condition is satisfied.
- Cells Sq through Tq are covered by at least one piece of cloth, and no other cells are covered by any cloth.
有 N 个单元格从左到右水平排列。从左起第 i 个单元格(1≤i≤N)称为单元格 i。
有 M 块布料。铺设第 i 块布料(1≤i≤M)将覆盖从单元格 Li 到单元格 Ri 的所有单元格。
回答 Q 个查询。对于第 q 个查询(1≤q≤Q),给定整数 Sq 和 Tq,请回答以下问题:
- 判断是否能从 M 块布料中恰好选择两块并铺设,使得满足如下条件:
- 单元格 Sq 到单元格 Tq 被至少一块布料覆盖,且除此之外的任何单元格均不被任何布料覆盖。
输入格式
The input is given from Standard Input in the following format:
N M
L1 R1
L2 R2
⋮
LM RM
Q
S1 T1
S2 T2
⋮
SQ TQ
输入从标准输入中按以下格式给出:
N M
L1 R1
L2 R2
⋮
LM RM
Q
S1 T1
S2 T2
⋮
SQ TQ
输出格式
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 1 and cloth 3.
For the third query, the condition can be satisfied by choosing cloth 1 and cloth 2.
For the second and fourth queries, no choice of two pieces of cloth can satisfy the condition.
Constraints
- 1≤N≤2×105
- 2≤M≤2×105
- 1≤Li≤Ri≤N
- 1≤Q≤2×105
- 1≤Sq≤Tq≤N
- All input values are integers.
样例 1 解释:
对于第一个查询,可以选择布料 1 和布料 3 来满足条件。
对于第三个查询,可以选择布料 1 和布料 2 来满足条件。
对于第二个和第四个查询,不存在任何两种布料的选择能够满足条件。
约束条件
- 1≤N≤2×105
- 2≤M≤2×105
- 1≤Li≤Ri≤N
- 1≤Q≤2×105
- 1≤Sq≤Tq≤N
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?