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 vector 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, vector
Returns:long long
Method signature:long long getSum(int n, int x0, int a, int b, vector query)
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
0)
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.
1)
5
123456789
987654321
1000000006
{0,1,2,3}
Returns: 733028692
X = {123456789, 259106858, 113077375, 244317875, 252176653}
2)
5000000
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