codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1702C.md (3094B)


      1 Source: https://codeforces.com/problemset/problem/1702/C
      2 
      3 C. Train and Queries
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Along the railroad there are stations indexed from $1$ to $10^9$. An express train always travels along a route consisting of $n$ stations with indices $u_1, u_2, \dots, u_n$, where ($1 \le u_i \le 10^9$). The train travels along the route from left to right. It starts at station $u_1$, then stops at station $u_2$, then at $u_3$, and so on. Station $u_n$ — the terminus.
     22 
     23 It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values $u_1, u_2, \dots, u_n$.
     24 
     25 You are given $k$ queries, each containing two different integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le 10^9$). For each query, determine whether it is possible to travel by train from the station with index $a_j$ to the station with index $b_j$.
     26 
     27 For example, let the train route consist of $6$ of stations with indices [$3, 7, 1, 5, 1, 4$] and give $3$ of the following queries:
     28 
     29 * $a_1 = 3$, $b_1 = 5$
     30 
     31   It is possible to travel from station $3$ to station $5$ by taking a section of the route consisting of stations [$3, 7, 1, 5$]. Answer: YES.
     32 * $a_2 = 1$, $b_2 = 7$
     33 
     34   You cannot travel from station $1$ to station $7$ because the train cannot travel in the opposite direction. Answer: NO.
     35 * $a_3 = 3$, $b_3 = 10$
     36 
     37   It is not possible to travel from station $3$ to station $10$ because station $10$ is not part of the train's route. Answer: NO.
     38 
     39 Input
     40 
     41 The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.
     42 
     43 The descriptions of the test cases follow.
     44 
     45 The first line of each test case is empty.
     46 
     47 The second line of each test case contains two integers: $n$ and $k$ ($1 \le n \le 2 \cdot 10^5, 1 \le k \le 2 \cdot 10^5$) —the number of stations the train route consists of and the number of queries.
     48 
     49 The third line of each test case contains exactly $n$ integers $u_1, u_2, \dots, u_n$ ($1 \le u_i \le 10^9$). The values $u_1, u_2, \dots, u_n$ are not necessarily different.
     50 
     51 The following $k$ lines contain two different integers $a_j$ and $b_j$ ($1 \le a_j, b_j \le 10^9$) describing the query with index $j$.
     52 
     53 It is guaranteed that the sum of $n$ values over all test cases in the test does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of $k$ values over all test cases in the test also does not exceed $2 \cdot 10^5$
     54 
     55 Output
     56 
     57 For each test case, output on a separate line:
     58 
     59 * YES, if you can travel by train from the station with index $a_j$ to the station with index $b_j$
     60 * NO otherwise.
     61 
     62 You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).
     63 
     64 Example
     65 
     66 Input
     67 
     68 ```
     69 3
     70 
     71 6 3
     72 
     73 3 7 1 5 1 4
     74 
     75 3 5
     76 
     77 1 7
     78 
     79 3 10
     80 
     81 3 3
     82 
     83 1 2 1
     84 
     85 2 1
     86 
     87 1 2
     88 
     89 4 5
     90 
     91 7 5
     92 
     93 2 1 1 1 2 4 4
     94 
     95 1 3
     96 
     97 1 4
     98 
     99 2 1
    100 
    101 4 1
    102 
    103 1 2
    104 ```
    105 
    106 Output
    107 
    108 ```
    109 YES
    110 NO
    111 NO
    112 YES
    113 YES
    114 NO
    115 NO
    116 YES
    117 YES
    118 NO
    119 YES
    120 ```
    121 
    122 Note
    123 
    124 The first test case is explained in the problem statement.