LimitedMemorySeries1 | Topcoder Archive

Problem Statement

You are given an array X that contains n integers. You are then given some queries. Each query is described by a single integer q. The answer to the query should be the q-th smallest element of the array X. Here, q is a 0-based index. (That is, q=0 means we want the smallest element, q=1 is the second smallest, and so on.)

Right now this task probably seems too easy. After all, you can simply sort the array X and then you'll be able to answer each query in constant time.

Here's the catch: the memory limit in this problem is really small. So small that you cannot even store the array X into memory.

You will be given the ints n, x0, a, and b. You will also be given the int[] query containing the queries.

Use the following pseudocode to generate the array X:

X[0] = x0
for i = 1 to n-1:
        X[i] = (X[i-1] * a + b) % (10^9+7).

(Watch out for integer overflow.)

Return the sum of answers to all the queries given in query.

Definition

Class:: LimitedMemorySeries1
Method:: getSum
Parameters:: int, int, int, int, int[]
Returns:: long
Method signature:: long getSum(int n, int x0, int a, int b, int[] query)
(be sure your method is public)

Notes

Due to some infrastructure limits the memory limit is set to 13 MB. Note that this should correspond to an actual memory limit of only 1 MB. If your solution allocates more than 1 MB of memory, it may exceed the memory limit.

Constraints

n will be between 1 and 5,000,000, inclusive.
x0, a and b will be between 0 and 1,000,000,006, inclusive.
query will contain between 1 and 100 elements, inclusive.
Each element in query will be between 0 and (n-1), inclusive.

Examples

```
5
```
```
100
```
```
1
```
```
5
```
```
{0,3}
```
```
Returns: 215
```
Using the pseudocode in the problem statement you should generate the array X = {100,105,110,115,120}. The answers to the two queries are 100 and 115. Hence, we should return 100 + 115 = 215.
```
5
```
```
123456789
```
```
987654321
```
```
1000000006
```
```
{0,1,2,3}
```
```
Returns: 733028692
```
X = {123456789, 259106858, 113077375, 244317875, 252176653}

482995837

512849030

120583724

{4854010,3139503,1855546,219904,846357,2624639,891260,217467,4940091,4802760,2424821,424076,
 3848272,2062765,2922407,4850301,1279972,4929307,2035456,3562859,1749594,4089499,3797495,1013980,
 1650805,1245213,3020379,4661668,427170,1176815,292944,2435328,420809,4170355,2635197,3940607,
 4311718,2098572,4868054,30319,4588969,1460677,1335028,3921495,3621970,4459335,966000,3686977,
 2316560,1634961,2280624,1940395,3321546,3168811,1856547,3859093,4340475,1382782,3482928,2517843,
 185008,1135373,2821050,3260484,4821220,1700954,3243343,2183615,394339,2630121,1811267,1060542,
 3898314,892312,2015580,11161,4965095,2128470,2320933,1095881,3938450,1887098,975426,2098073,3300937,
 1145560,2894728,1026181,3259403,4509345,3610224,3584456,1877483,2665752,2243671,616205,504849,3068426,
 1471925,4144568}

Returns: 49684994148

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.