SAC '22 Code Challenge 5 P4 - Querying Intervals

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

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

Given N intervals of [l_i, r_i], answer Q queries.

Each query comes in the form L_i R_i, where you will check if you can move from L_i to 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 intervals).

Output Y if you can cover the range [L_i, R_i]; otherwise, output N if you cannot cover the range.

Can you help Mr. DeMello?


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

Input Specification

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

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

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

Output Specification

Output Q lines, the answers to the queries.

Sample Input

4 3
7 9
-5 4
10 14
16 19
8 10
-5 -5
11 18

Sample Output



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

    Is there any overlaps in the intervals?