Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Powerful Array

By Limon_88 · Limits 1s, 512 MB

You are given an array A of N integers . Now you have to process Q queries in this array. Each query is represented by two number id and K. You have to perform some operations for each query . Each operation is changes id to A[id]+K+id which take t time to do it. There operations are applied until id becomes greater than n. In each query you have to print the total time is being taken to perform all operation in each query.


The first line of the input contains two integer N (1 ≤ N ≤ 20000) and t (1 ≤ t ≤ 10) denoting the size of the array and time.

Next line contain N integers Ai (1 ≤ Ai≤ N) which are the elements of the array.

Next line contains an integer Q (1 ≤ Q ≤ 105)denoting the number of queries.

Each of the following next Q line contains two integer id (1 ≤ id ≤ N) and K (1 ≤ K ≤ N).


Print — the answer of each query in a separate line


3 5
1 1 1
1 1
2 1
3 1

Consider first example:
In first query after first operation id = 3, after second operation id = 5. Total Time = 2 * 5 =10
In second query id is greater than n after the first operation. So time is only 5
In last query id is greater than n after the first operation. So time is only 5



100% Solution Ratio

Arl_88Earliest, 1M ago

Arl_88Fastest, 0.1s

Arl_88Lightest, 26 MB

Arl_88Shortest, 1179B


Login to submit

Related Contests

SEC Intra Campus Programming Contest, CSE Fest 2020 Ended at 2020-02-19 11:02:00 +0000 UTC