/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
N 個のマスが左右一列に並んでいます。左から i 番目 (1\le i\le N) のマスをマス i と呼びます。
M 枚の布があり、布 i (1\le i\le M) を敷くとマス L_i からマス R_i までを覆うことができます。
Q 個のクエリに答えてください。q 番目 (1\le q\le Q) のクエリでは整数 S_q,T_q が与えられるので、以下の問題に答えてください。
- M 枚の布の中からちょうど 2 枚の布を選んで敷くことで、以下の条件を満たすことができるか判定せよ。
- マス S_q からマス T_q までは 1 枚以上の布で覆われており、それ以外のマスは布で覆われていない。
制約
- 1\le N\le 2\times 10^5
- 2\le M\le 2\times 10^5
- 1\le L_i \le R_i\le N
- 1\le Q\le 2\times 10^5
- 1\le S_q \le T_q\le N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M L_1 R_1 L_2 R_2 \vdots L_M R_M Q S_1 T_1 S_2 T_2 \vdots S_Q T_Q
出力
各クエリに対する答えを改行区切りで出力せよ。
各クエリでは、条件を満たすように 2 枚の布を選ぶことができる場合は 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
1 番目のクエリでは布 1 と布 3 を選ぶことで条件を満たすことができます。
3 番目のクエリでは布 1 と布 2 を選ぶことで条件を満たすことができます。
2,4 番目のクエリではどの 2 枚の布を選んでも条件を満たすことはできません。
入力例 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
Score : 475 points
Problem Statement
There are N cells arranged in a horizontal row. The i-th cell from the left (1 \le i \le N) is called cell i.
There are M pieces of cloth. Laying cloth i (1 \le i \le M) covers cells L_i through R_i.
Answer Q queries. For the q-th query (1 \le q \le Q), integers S_q and T_q 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 S_q through T_q are covered by at least one piece of cloth, and no other cells are covered by any cloth.
Constraints
- 1 \le N \le 2 \times 10^5
- 2 \le M \le 2 \times 10^5
- 1 \le L_i \le R_i \le N
- 1 \le Q \le 2 \times 10^5
- 1 \le S_q \le T_q \le N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M L_1 R_1 L_2 R_2 \vdots L_M R_M Q S_1 T_1 S_2 T_2 \vdots S_Q T_Q
Output
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.
Sample Input 1
4 3 1 3 1 1 2 4 4 1 4 2 4 1 3 1 1
Sample Output 1
Yes No Yes No
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.
Sample Input 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
Sample Output 2
Yes No No Yes Yes No Yes Yes No No