Problem Statement
Time limit: 8 seconds
Two numbers are close if their absolute difference does not exceed D.
Given a collection of cards, each containing a number, its proximity score is the number of unordered pairs of cards such that their numbers are close.
For instance, if your cards have the numbers {3, 3, 4, 9, 6} and D = 2, the proximity score is 4: the pair of threes is close to each other, each three is close to the four, and the four is close to the six.
If we had the same collection but D was 6 or more, the proximity score would be 10 as each possible pair of cards would contain two numbers that are close.
You are given a sequence of cards that contain the numbers C[0..N-1] in this order. You are also given a sequence of Q queries. Query i describes one contiguous segment of the card sequence: cards at positions A[i] to B[i], inclusive.
For each query, determine the proximity score of the cards that form the given segment. Return the sum of answers to all queries, modulo 10^9 + 7.
In order to keep the input small, the numbers on the cards and the queries are both pseudorandom. Please use the pseudocode below to generate them. Note that all card numbers will be smaller than M and all queries will be intervals that contain at least L cards.
state = seed
A, B = two arrays of length Q
C = an array of length N
for i = 0 to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
C[i] = state modulo M
for i = 0 to Q-1:
state = (state * 1103515245 + 12345) modulo 2^31
ql = L + (state modulo (N-L+1))
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = state modulo (N-ql+1)
B[i] = A[i] + ql - 1
Definition
- Class:
- Proximity
- Method:
- count
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int count(int N, int Q, int D, int M, int L, int seed)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 100,000, inclusive.
- Q will be between 1 and 100,000, inclusive.
- D will be between 0 and 100,000, inclusive.
- M will be between 1 and 100,000, inclusive.
- L will be between 1 and N, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
10
5
100
100
1
47
Returns: 27
The numbers on cards: C = {8, 5, 98, 91, 48, 33, 50, 27, 76, 37} The arrays that describe the queries: A = {3, 1, 7, 5, 5} B = {9, 1, 9, 7, 5} As D >= M, it's clear that for each query all possible pairs of cards are close, and thus the proximity score of a collection of x cards is x*(x-1)/2. Hence, our five queries have proximity scores 21, 0, 3, 3, and 0. The sum of all answers is 27.
10
5
100
100
1
42
Returns: 78
Same parameters, different seed. Here the generated arrays look as follows: C = {27, 64, 53, 6, 35, 32, 33, 66, 59, 52} A = {2, 1, 4, 0, 6} B = {7, 4, 7, 9, 9} The answers to queries are 15, 6, 6, 45, and 6, for a total of 78.
10
5
0
100
1
42
Returns: 0
Same arrays as in the previous example, but as now D = 0 and all the values in C are distinct, each query has the answer zero.
10
5
1
100
1
42
Returns: 4
Same arrays as in the previous two examples, but now D = 1. The numbers 32 and 33 are now close, as are the numbers 52 and 53. The queries that contain one or both of these pairs now have positive answers.
99997
99993
0
1
99997
12345
Returns: 999550455
All cards have zeros on them. Each pair of cards is close. Each query is the entire array. The answer to each query is N*(N-1)/2. The correct return value is Q times that, modulo 10^9 + 7.
99993
99997
40000
99999
5000
2333235
Returns: 275015898
99360
99064
15624
24819
7310
175701600
Returns: 896820127
99814
99428
1
782
33366
1355395163
Returns: 820003407
99581
99437
188
30874
136
1607036031
Returns: 447662950
99733
99704
3448
6050
2
1434210114
Returns: 573640422
99100
99371
6167
1488
1471
2023059399
Returns: 695860125
99762
99112
13976
12107
438
172270288
Returns: 375783310
99495
99319
6227
5029
112
2084771948
Returns: 856025617
99259
99985
30
686
4
1141387247
Returns: 542357306
99523
99832
61316
17471
497
1352884873
Returns: 15516077
99849
99022
182
30527
43
2017745344
Returns: 355362735
99943
99203
19
3457
4981
1146177193
Returns: 770285253
99454
99000
14
1780
1
179122525
Returns: 275356673
99143
99185
45950
100000
1
752144434
Returns: 209845153
99855
99154
1119
4597
5104
95408474
Returns: 448253551
99090
99309
3
5334
297
2109919775
Returns: 230799924
99350
99569
2
60138
3288
2101334812
Returns: 90318400
99612
99143
4
100000
1
284290351
Returns: 746726687
99800
99808
1013
1526
3404
716905769
Returns: 468341014
99473
99023
15
100000
1
1232890504
Returns: 644726901
99041
99790
503
37254
15
1554617535
Returns: 975195717
99592
99319
11548
1234
926
1429174780
Returns: 628056387
99551
99856
2493
1896
2253
1502298833
Returns: 980733881
99596
99885
3
12359
101
898538742
Returns: 531461384
99476
99871
967
100000
2
2060295352
Returns: 501021326
99000
99028
15686
99316
616
1301697396
Returns: 825517344
99126
99955
59
32687
12034
1130011384
Returns: 92624395
99320
99568
1
89063
4446
780112910
Returns: 743995249
99627
99951
36
100000
2
1983085133
Returns: 609301158
99180
99952
4132
2346
4102
1650855086
Returns: 574725684
99511
99759
28613
1844
9
1805133931
Returns: 527906425
99421
99963
10
100000
19455
1698673775
Returns: 728586570
99537
99517
1909
6687
4707
569139255
Returns: 72083484
99971
99729
54595
1541
38843
1533974457
Returns: 81429744
99993
99030
4762
5822
412
488502684
Returns: 69788171
99935
99575
3
4047
231
2036088828
Returns: 559966961
99007
99603
6023
19880
1155
674631869
Returns: 112566403
99604
99108
174
1314
42
331716879
Returns: 249399388
99094
99128
6949
1873
736
1489995248
Returns: 548960718
99787
99092
1232
718
26
390384469
Returns: 913432920
99853
99326
13961
61546
14960
2107368689
Returns: 777509478
99023
99199
1124
39394
20448
413576938
Returns: 169490242
99866
99342
9158
22527
15872
2040058862
Returns: 842901722
99709
99528
11
4312
54081
609918436
Returns: 127969613
99691
99167
586
817
2
1100292491
Returns: 963729335
99352
99924
91
28530
22
1921564817
Returns: 36262015
99630
99035
818
40029
15045
1492517263
Returns: 389042962
99774
99509
279
95646
463
251147389
Returns: 213866187
99893
99024
5658
56809
6
1456006488
Returns: 606753397
99451
99886
4
100000
5
879293777
Returns: 819925269
99232
99951
15935
6526
1
50952394
Returns: 529934527
99257
99546
111
93619
1844
164647511
Returns: 26539356
99689
99661
13524
16629
8
1335612918
Returns: 923436296
99810
99049
64
562
7897
820206654
Returns: 22036458
99091
99989
458
17622
6
1336545990
Returns: 725401573
99053
99624
31569
54566
6
1805700976
Returns: 871318099
99382
99960
14
44329
542
130904518
Returns: 484696854
99588
99998
80
4802
1
1836672899
Returns: 67578084
99426
99724
10282
3586
24990
633779308
Returns: 491042892
99076
99040
160
1059
19
546676137
Returns: 196694572
99626
99874
940
68610
41
993117026
Returns: 243905085
99991
99991
7470
99991
90000
12345
Returns: 994160419
100000
100000
10000
100000
12
100000
Returns: 580518546
100000
100000
100000
100000
111
168497
Returns: 981324492