[Solution] Train and Queries solution codeforces

Train and Queries solution codeforces – Along the railroad there are stations indexed from 11 to 109109. An express train always travels along a route consisting of 𝑛n stations with indices 𝑢1,𝑢2,,𝑢𝑛u1,u2,…,un, where (1𝑢𝑖1091≤ui≤109). The train travels along the route from left to right. It starts at station 𝑢1u1, then stops at station 𝑢2u2, then at 𝑢3u3, and so on. Station 𝑢𝑛un — the terminus.

Table of Contents

[Solution] Train and Queries solution codeforces

It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values 𝑢1,𝑢2,,𝑢𝑛u1,u2,…,un.

You are given 𝑘k queries, each containing two different integers 𝑎𝑗aj and 𝑏𝑗bj (1𝑎𝑗,𝑏𝑗1091≤aj,bj≤109). For each query, determine whether it is possible to travel by train from the station with index 𝑎𝑗aj to the station with index 𝑏𝑗bj.

For example, let the train route consist of 66 of stations with indices [3,7,1,5,1,43,7,1,5,1,4] and give 33 of the following queries:

  • 𝑎1=3a1=3𝑏1=5b1=5It is possible to travel from station 33 to station 55 by taking a section of the route consisting of stations [3,7,1,53,7,1,5]. Answer: YES.
  • 𝑎2=1a2=1𝑏2=7b2=7You cannot travel from station 11 to station 77 because the train cannot travel in the opposite direction. Answer: NO.
  • 𝑎3=3a3=3𝑏3=10b3=10It is not possible to travel from station 33 to station 1010 because station 1010 is not part of the train’s route. Answer: NO.

[Solution] Train and Queries solution codeforces

The first line of the input contains an integer 𝑡t (1𝑡1041≤t≤104) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case is empty.

The second line of each test case contains two integers: 𝑛n and 𝑘k (1𝑛2105,1𝑘21051≤n≤2⋅105,1≤k≤2⋅105) —the number of stations the train route consists of and the number of queries.

The third line of each test case contains exactly 𝑛n integers 𝑢1,𝑢2,,𝑢𝑛u1,u2,…,un (1𝑢𝑖1091≤ui≤109). The values 𝑢1,𝑢2,,𝑢𝑛u1,u2,…,un are not necessarily different.

The following 𝑘k lines contain two different integers 𝑎𝑗aj and 𝑏𝑗bj (1𝑎𝑗,𝑏𝑗1091≤aj,bj≤109) describing the query with index 𝑗j.

It is guaranteed that the sum of 𝑛n values over all test cases in the test does not exceed 21052⋅105. Similarly, it is guaranteed that the sum of 𝑘k values over all test cases in the test also does not exceed 21052⋅105

[Solution] Train and Queries solution codeforces

For each test case, output on a separate line:

  • YES, if you can travel by train from the station with index 𝑎𝑗aj to the station with index 𝑏𝑗bj
  • NO otherwise.

You can output YES and NO in any case (for example, strings yEsyesYes and YES will be recognized as a positive response).

Example
input

Copy
3

6 3
3 7 1 5 1 4
3 5
1 7
3 10

3 3
1 2 1
2 1
1 2
4 5

7 5
2 1 1 1 2 4 4
1 3
1 4
2 1
4 1
1 2

[Solution] Train and Queries solution codeforces

output

Copy
YES
NO
NO
YES
YES
NO
NO
YES
YES
NO
YES
Note

The first test case is explained in the problem statement.

 

For Solution

Click Here

Leave a Comment