All Tracks Algorithms Problem

Utkarsh and Tiresome RMQ
Tag(s):

Algorithms, Hard, Sqrt-Decomposition

Problem
Editorial
Analytics

Utkarsh loves finding maximum integers in a given sequence. But this love is not always accompanied with proper knowledge. His teacher once gave him a homework problem and due to his poor knowledge he was not able to solve it. Its 6 in the morning and he has just 2 hours left to solve the problem. Can you help him solve the problem.

He was given an array $$A$$ consisting of $$N$$ integers and integers $$B$$ and $$M$$. He had to answer $$Q$$ queries. Each query is of the form
$$x\space y$$ : Print the maximum integer among {$$A_x +B,\space A_{x-y} +2B, \space A_{x-2y} +3B,..., \space A_{x-(M-1)y} +MB $$}


$$INPUT$$
First line contains four integers $$N, Q, B, M$$.
Second line contains $$N$$ integers of array $$A$$.
Next $$Q$$ lines describe $$Q$$ queries in the form $$x\space y$$.


$$OUTPUT$$
Print the answer to each query.


$$CONSTRAINTS$$
$$1 ≤ N,Q,M ≤ 10^5$$
$$-10^9 ≤ A_i\space, B ≤ 10^9$$
$$1 ≤ x,y ≤N$$

Note: Array A is 1-indexed. Do not consider elements in the list if corresponding index in array is non-positive, i.e., do not consider $$A_{x - (i-1)\times y} + iB $$ if $$ (x - (i-1)\times y) ≤ 0 $$

SAMPLE INPUT
8 8 3 3
4 8 7 4 1 10 1 12
1 1
2 1
3 1
4 2
5 3
6 1
7 2
8 1
SAMPLE OUTPUT
7
11
14
14
14
13
16
19
Explanation

The list of integers for each query: maximum

  1. {4+3} : 7
  2. {8+3, 4+6}: 11
  3. {7+3, 8+6, 4+9}:14
  4. {4+3, 8+6}: 14
  5. {1+3, 8+6}: 14
  6. {10+3, 1+6, 4+9}: 13
  7. {1+3, 1+6, 7+9} : 16
  8. {12+3, 1+6, 10+9}: 19

(Note that in some lists less than three elements are considered because their corresponding array index is non positive)

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications