SAC '22 Code Challenge 5 P4 - Querying Intervals

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Since Mr. DeMello hates flavour text, he decides to give you a sleek statement instead:

Given $N$ $N$ intervals of $[l_i, r_i]$ $[l_{i}, r_{i}]$ , answer $Q$ $Q$ queries.

Each query comes in the form L_i R_i, where you will check if you can move from $L_i$ $L_{i}$ to $R_i$ $R_{i}$ while always being on an interval (i.e., every integer on that interval must be contained in at least one of the $N$ $N$ intervals).

Output Y if you can cover the range $[L_i, R_i]$ $[L_{i}, R_{i}]$ ; otherwise, output N if you cannot cover the range.

Can you help Mr. DeMello?

Constraints

$1 \le N, Q \le 100\,000$ $1 \leq N, Q \leq 100 000$

$-10^9 \le l_i \le r_i \le 10^9$ $- 10^{9} \leq l_{i} \leq r_{i} \leq 10^{9}$

$-10^9 \le L_i \le R_i \le 10^9$ $- 10^{9} \leq L_{i} \leq R_{i} \leq 10^{9}$

Input Specification

The first line will contain two integers, $N$ $N$ and $Q$ $Q$ , the number of intervals and the number of queries, respectively.

The next $N$ $N$ lines will contain two integers, $l_i$ $l_{i}$ and $r_i$ $r_{i}$ , the endpoints of the $i^\text{th}$ $i^{th}$ interval.

The next $Q$ $Q$ lines will contain two integers, $L_i$ $L_{i}$ and $R_i$ $R_{i}$ , the endpoints of the $i^\text{th}$ $i^{th}$ query.

Output Specification

Output $Q$ $Q$ lines, the answers to the queries.

Sample Input

Copy

Sample Output

Copy

Y
Y
N

Comments

0

ColonelBy_team10 commented on Aug. 26, 2022, 12:37 a.m.

Is there any overlaps in the intervals?