codeforces-scrape

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

1179A.md (2711B)


      1 Source: https://codeforces.com/problemset/problem/1179/A
      2 
      3 A. Valeriy and Deque
      4 
      5 time limit per test
      6 
      7 6 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 Recently, on the course of algorithms and data structures, Valeriy learned how to use a deque. He built a deque filled with $n$ elements. The $i$-th element is $a_i$ ($i$ = $1, 2, \ldots, n$). He gradually takes the first two leftmost elements from the deque (let's call them $A$ and $B$, respectively), and then does the following: if $A \gt B$, he writes $A$ to the beginning and writes $B$ to the end of the deque, otherwise, he writes to the beginning $B$, and $A$ writes to the end of the deque. We call this sequence of actions an operation.
     22 
     23 For example, if deque was $[2, 3, 4, 5, 1]$, on the operation he will write $B=3$ to the beginning and $A=2$ to the end, so he will get $[3, 4, 5, 1, 2]$.
     24 
     25 The teacher of the course, seeing Valeriy, who was passionate about his work, approached him and gave him $q$ queries. Each query consists of the singular number $m_j$ $(j = 1, 2, \ldots, q)$. It is required for each query to answer which two elements he will pull out on the $m_j$-th operation.
     26 
     27 Note that the queries are independent and for each query the numbers $A$ and $B$ should be printed in the order in which they will be pulled out of the deque.
     28 
     29 Deque is a data structure representing a list of elements where insertion of new elements or deletion of existing elements can be made from both sides.
     30 
     31 Input
     32 
     33 The first line contains two integers $n$ and $q$ ($2 \leq n \leq 10^5$, $0 \leq q \leq 3 \cdot 10^5$) — the number of elements in the deque and the number of queries. The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$, where $a_i$ $(0 \leq a_i \leq 10^9)$ — the deque element in $i$-th position. The next $q$ lines contain one number each, meaning $m_j$ ($1 \leq m_j \leq 10^{18}$).
     34 
     35 Output
     36 
     37 For each teacher's query, output two numbers $A$ and $B$ — the numbers that Valeriy pulls out of the deque for the $m_j$-th operation.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5 3
     45 1 2 3 4 5
     46 1
     47 2
     48 10
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 1 2
     55 2 3
     56 5 2
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 2 0
     63 0 0
     64 ```
     65 
     66 Output
     67 
     68 Note
     69 
     70 Consider all 10 steps for the first test in detail:1. $[1, 2, 3, 4, 5]$ — on the first operation, $A$ and $B$ are $1$ and $2$, respectively.
     71 
     72    So, $2$ we write to the beginning of the deque, and $1$ — to the end.
     73 
     74    We get the following status of the deque: $[2, 3, 4, 5, 1]$.
     75 2. $[2, 3, 4, 5, 1] \Rightarrow A = 2, B = 3$.
     76 3. $[3, 4, 5, 1, 2]$
     77 4. $[4, 5, 1, 2, 3]$
     78 5. $[5, 1, 2, 3, 4]$
     79 6. $[5, 2, 3, 4, 1]$
     80 7. $[5, 3, 4, 1, 2]$
     81 8. $[5, 4, 1, 2, 3]$
     82 9. $[5, 1, 2, 3, 4]$
     83 10. $[5, 2, 3, 4, 1] \Rightarrow A = 5, B = 2$.