|
||||||||||
SwimmerTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1069 Accepted Submission(s): 277 Problem Description One day, $n$ of swimmers hold a wonderful competition in a swimming pool. There are $n$ lanes in the swimming pool numbered from $1$ to $n$ , and the their lengths are all $m$ meters. Swimmers are also numbered from $1$ to $n$, and swimmer $i$ occpies lane $i$. The swimmers will start at position $0$, and turn back immediately when arriving at the turn line at position $m$. They will keep swimming. The speed of swimmers may be different. The speed of the swimmer $i$ is $x_i$ meters per second. You need to answer $q$ questions: each question gives two integers $p$ and $k$, asking for the position of swimmer $k$ after $p$ seconds. Input The first line contains three integers $n , m, q$ $(1 \le n \le 10^{6}, 1 \le m \le 10^{9}, 1 \le q \le 10^{6})$, indicating the number of lanes, the length of lanes and the number of questions, respectively. The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ $(1 \le x_{i} \le 10^{9})$, indicating the speed of each swimmer. Each of the following $q$ lines contains two integers $p_i, k_i$ $(0 \le p_i \le 10^{9}, 1 \le k_i \le n)$ representing the $i$-th question. Output Output $q$ lines. Each line contains a single integer, which is the answer of the $i$-th question. Sample Input
Sample Output
Source | ||||||||||
|