LimitedMemorySeries1

SRM 675 · 2015-11-03 · by cgy4ever

SRM 675 · 2015-11-03 · by cgy4ever · Search

Show categories

Class Name: LimitedMemorySeries1

Return Type: long

Method Name: getSum

Arg Types: (int, int, int, int, vector<int>)

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.

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}

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

1
1
1
1
{0}
Returns: 1

5000000
9283721
5235235
1546532
{3462691,855833,553671,1990051,3686326,2801888,2508455,1190388,403166,3876851,3048240,2168407,3257209,1637115,3724211,2282966,4218501,1565262,1168701,3991378,1705255,4952401,2791595,333787,4022053,4690590,4687228,974991,4044838,1487334,3621119,980055,4788745,2657201,307639,931461,3745432,4001272,1224744,4092625,1044467,1546296,1599061,690753,3271718,796750,1975745,2143997,3693472,4455550,1505598,2530738,3653023,1628438,3618730,739623,2768440,2992148,1886172,807216,3640120,3917983,1559407,4403308,3516658,1932176,2321962,2070958,4994318,2398602,3680512,2864136,136905,1155377,1005395,98751,1829019,4307884,3069354,432191,4678862,183820,4002584,4061019,4285998,906618,4483166,194987,3599915,2096107,580347,651205,2485272,3379371,414058,855299,409113,3212565,4189512,280215}
Returns: 48409676366

Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LimitedMemorySeries1 with a public method long long getSum(int n, int x0, int a, int b, vector<int> query) · 23 test cases · 2 s / 256 MB per case