codeforces-scrape

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

1719C.md (2957B)


      1 Source: https://codeforces.com/problemset/problem/1719/C
      2 
      3 C. Fighting Tournament
      4 
      5 time limit per test
      6 
      7 2 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 Burenka is about to watch the most interesting sporting event of the year — a fighting tournament organized by her friend Tonya.
     22 
     23 $n$ athletes participate in the tournament, numbered from $1$ to $n$. Burenka determined the strength of the $i$-th athlete as an integer $a_i$, where $1 \leq a_i \leq n$. All the strength values are different, that is, the array $a$ is a permutation of length $n$. We know that in a fight, if $a_i \gt a_j$, then the $i$-th participant always wins the $j$-th.
     24 
     25 The tournament goes like this: initially, all $n$ athletes line up in ascending order of their ids, and then there are infinitely many fighting rounds. In each round there is exactly one fight: the first two people in line come out and fight. The winner goes back to the front of the line, and the loser goes to the back.
     26 
     27 Burenka decided to ask Tonya $q$ questions. In each question, Burenka asks how many victories the $i$-th participant gets in the first $k$ rounds of the competition for some given numbers $i$ and $k$. Tonya is not very good at analytics, so he asks you to help him answer all the questions.
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 10^5$, $1 \leq q \leq 10^5$) — the number of tournament participants and the number of questions.
     34 
     35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — the array $a$, which is a permutation.
     36 
     37 The next $q$ lines of a test case contain questions. Each line contains two integers $i$ and $k$ ($1 \leq i \leq n$, $1 \leq k \leq 10^9$) — the number of the participant and the number of rounds.
     38 
     39 It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$.
     40 
     41 Output
     42 
     43 For each Burenka's question, print a single line containing one integer — the answer to the question.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 3 1
     53 
     54 3 1 2
     55 
     56 1 2
     57 
     58 4 2
     59 
     60 1 3 4 2
     61 
     62 4 5
     63 
     64 3 2
     65 
     66 5 2
     67 
     68 1 2 3 5 4
     69 
     70 5 1000000000
     71 
     72 4 6
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 2
     79 0
     80 1
     81 0
     82 4
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, the first numbered athlete has the strength of $3$, in the first round he will defeat the athlete with the number $2$ and the strength of $1$, and in the second round, the athlete with the number $3$ and the strength of $2$.
     88 
     89 In the second test case, we list the strengths of the athletes fighting in the first $5$ fights: $1$ and $3$, $3$ and $4$, $4$ and $2$, $4$ and $1$, $4$ and $3$. The participant with the number $4$ in the first $5$ rounds won $0$ times (his strength is $2$). The participant with the number $3$ has a strength of $4$ and won $1$ time in the first two fights by fighting $1$ time.