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 \le N, Q \le 100\,000~

$-10^9 \le l_i \le r_i \le 10^9$ ~-10^9 \le l_i \le r_i \le 10^9~

$-10^9 \le L_i \le R_i \le 10^9$ ~-10^9 \le L_i \le R_i \le 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^\text{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^\text{th}~ query.

Output Specification

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

Sample Input

Sample Output

Y
Y
N

Comments

0

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

Is there any overlaps in the intervals?