QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#455751#1877. Matryoshka DollsmakravAC ✓1741ms326944kbC++174.7kb2024-06-26 19:21:532024-06-26 19:21:54

Judging History

你现在查看的是最新测评结果

  • [2024-06-26 19:21:54]
  • 评测
  • 测评结果：AC
  • 用时：1741ms
  • 内存：326944kb
查看
  • [2024-06-26 19:21:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int K = 600;
const int N = 100010;

int ans_block[(N + K) / K][K][K];
int SPMIN[(N + K) / K][10][K], SPMAX[(100010 + K) / K][10][K];
int nxt[(N + K) / K][100010];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    vector<int> Log2(n + 1, 0);
    for (int i = 2; i <= n; i++) Log2[i] = Log2[i / 2] + 1; 
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<pair<int, int>> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = {a[i], i};
    }
    sort(b.begin(), b.end());
    vector<int> pos(n + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]] = i;
    }
    vector<int> bl(n, -1);
    int ind= -1;
    for (int i = 0; i < n; i += K) {
        ind++;
        vector<int> ppos;
        for (int j = i; j < min(n, i + K); j++) {
            bl[b[j].second] = ind;
            ppos.push_back(b[j].second);
        }
        nxt[ind][n] = n + 1;
        int INDD = ppos.size() - 1;
        for (int j = n - 1; j >= 0; j--) {
            nxt[ind][j] = nxt[ind][j + 1];
            if (bl[j] == ind) nxt[ind][j] = INDD--;
        }
        sort(ppos.begin(), ppos.end());
        vector<vector<int>> bd_right(ppos.size(), vector<int>(ppos.size())), bd_left(ppos.size(), vector<int>(ppos.size()));
        for (int I = 0; I < ppos.size() - 1; I++) {
            bd_right[I][I] = 1e9;
            bd_left[I][I] = 1e9;
            for (int j = I + 1; j < ppos.size(); j++) {
                bd_right[I][j] = bd_right[I][j - 1];
                bd_left[I][j] = bd_left[I][j - 1];
                if (a[ppos[j]] > a[ppos[I]] && bd_right[I][j] > a[ppos[j]] - a[ppos[I]]) {
                    bd_right[I][j] = a[ppos[j]] - a[ppos[I]];
                }
                if (a[ppos[j]] < a[ppos[I]] && bd_left[I][j] > a[ppos[I]] - a[ppos[j]]) {
                    bd_left[I][j] = a[ppos[I]] - a[ppos[j]];
                }
            }
        }
        for (int I = 0; I < ppos.size(); I++) {
            SPMIN[ind][0][I] = a[ppos[I]];
            SPMAX[ind][0][I] = a[ppos[I]];
        }
        for (int j = 1; j < 10; j++) {
            for (int I = 0; I + (1 << j) - 1 < ppos.size(); I++) {
                SPMIN[ind][j][I] = min(SPMIN[ind][j - 1][I], SPMIN[ind][j - 1][I + (1 << (j - 1))]);
                SPMAX[ind][j][I] = max(SPMAX[ind][j - 1][I], SPMAX[ind][j - 1][I + (1 << (j - 1))]);
            }
        }
        vector<vector<int>> ans(ppos.size(), vector<int>(ppos.size()));
        for (int I = ppos.size() - 1; I >= 0; I--) {
            ans[I][I] = 0;
            ans_block[ind][I][I] = ans[I][I];
            for (int j = I - 1; j >= 0; j--) {
                ans[j][I] = ans[j + 1][I];
                int rg = (bd_right[j][I] == 1e9 ? -1 : a[ppos[j]] + bd_right[j][I]);
                int lf = (bd_left[j][I] == 1e9 ? -1 : a[ppos[j]] - bd_left[j][I]);
                if (rg != -1) ans[j][I] += abs(pos[rg] - pos[a[ppos[j]]]);
                if (lf != -1) ans[j][I] += abs(pos[lf] - pos[a[ppos[j]]]);
                if (lf != -1 && rg != -1) ans[j][I] -= abs(pos[lf] - pos[rg]);
                ans_block[ind][j][I] = ans[j][I];
            }
        }
    }
    vector<vector<pair<int, int>>> qrs(n);
    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r; l--; r--;
        qrs[r].push_back({l, i});
    }
    auto getmax = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return max(SPMAX[block][lg][l], SPMAX[block][lg][r - (1 << lg) + 1]);
    };
    auto getmin = [&](int block, int l, int r) {
        int lg = Log2[r - l + 1];
        return min(SPMIN[block][lg][l], SPMIN[block][lg][r - (1 << lg) + 1]);
    };
    int IND = 0;

    ind++;
    vector<int> last(ind, -1);
    vector<ll> ANSW(q);
    vector<int> cnt(ind);
    for (int r = 0; r < n; r++) {
        last[bl[r]] = cnt[bl[r]]++;
        for (auto [L, idx] : qrs[r]) {
            ll ANS = 0;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j] && last[j] != -1) {
                    ANS += ans_block[j][nxt[j][L]][last[j]];
                }
            }
            vector<int> lol;
            int LAST = -1;
            for (int j = 0; j < ind; j++) {
                if (nxt[j][L] <= last[j]&&last[j] > -1) {
                    int RG = getmax(j, nxt[j][L], last[j]), LF = getmin(j, nxt[j][L], last[j]);
                    if (LAST != -1) ANS += abs(pos[LF] - pos[LAST]);
                    LAST = RG;
                }
            }

            ANSW[idx] = ANS;
            IND++;
        }
    }
    for (auto &u : ANSW) cout << u << '\n';

    return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 9676kb

input:

5 5
1 5 2 4 3
1 5
1 4
1 3
1 2
1 1

output:

7
5
3
1
0

result:

ok 5 number(s): "7 5 3 1 0"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9896kb

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 277ms
memory: 317392kb

input:

100000 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...

output:

4999950000

result:

ok 1 number(s): "4999950000"

Test #4:

score: 0
Accepted
time: 1ms
memory: 9964kb

input:

20 1
12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7
9 18

output:

36

result:

ok 1 number(s): "36"

Test #5:

score: 0
Accepted
time: 0ms
memory: 9676kb

input:

20 10
5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9
7 11
7 13
7 17
11 15
1 7
4 6
1 5
6 14
3 5
9 9

output:

7
16
34
9
20
3
8
22
3
0

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 1ms
memory: 9936kb

input:

20 50
7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14
3 6
5 15
11 20
10 18
9 20
3 17
13 20
16 17
3 20
4 17
15 18
5 19
3 14
8 20
2 20
1 4
15 19
16 20
5 13
14 17
4 10
6 16
8 16
1 12
4 9
11 15
4 20
8 11
3 16
7 7
3 11
3 7
4 4
5 12
6 20
3 14
6 19
6 19
2 14
2 12
5 6
4 6
8 15
10 19
4 14
1 16
1 20
2 13
3...

output:

6
48
36
24
46
74
17
1
104
64
5
68
44
58
130
5
9
8
30
7
13
48
26
38
11
8
92
5
70
0
28
9
0
20
80
44
58
58
48
36
1
2
20
28
34
76
136
46
1
28

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 1ms
memory: 9776kb

input:

20 100
4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2
4 19
1 6
6 19
4 6
2 17
1 5
11 13
1 15
9 17
9 15
7 20
3 19
10 19
1 10
11 17
10 17
2 18
17 20
12 19
1 3
5 17
7 13
6 18
10 20
1 6
2 17
5 9
4 13
11 13
2 20
7 13
12 17
5 19
17 20
11 19
3 15
3 5
5 11
1 17
10 15
16 20
1 6
2 19
4 12
5 18
9 17
3 6
12 ...

output:

76
16
57
3
84
10
3
74
31
19
59
80
40
44
16
26
94
5
26
2
54
17
53
44
16
84
8
32
3
106
17
12
68
5
30
48
2
16
102
14
9
16
98
28
64
31
6
1
54
20
26
31
74
5
26
3
66
32
36
59
1
26
6
33
35
5
57
1
1
57
24
6
10
68
36
41
34
0
12
8
11
2
62
12
41
10
5
25
0
60
0
44
25
12
8
2
16
36
8
1

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 9688kb

input:

20 228
7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15
7 20
2 20
10 13
14 19
1 9
12 20
17 19
9 20
10 12
14 17
4 15
7 16
5 12
13 16
16 18
7 18
1 11
7 17
2 20
6 8
9 17
12 18
7 18
3 4
7 13
1 4
6 12
6 10
3 17
3 4
5 14
7 13
9 20
6 20
2 4
14 17
17 20
1 7
19 20
4 20
14 15
12 16
4 6
4 15
10 11
2 16
2 20
...

output:

66
136
5
9
32
30
2
42
3
5
62
40
28
5
2
50
44
44
136
3
20
14
50
1
16
5
18
10
74
1
44
16
42
90
3
5
3
13
1
108
1
6
3
62
1
94
136
3
14
42
3
80
26
6
54
7
26
26
31
1
74
38
15
14
52
26
14
6
4
7
3
2
70
13
2
44
6
76
26
90
1
66
108
0
28
16
132
18
7
3
14
48
7
15
1
8
9
22
9
18
36
5
70
44
42
3
1
42
0
3
3
8
3
62
...

result:

ok 228 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 9944kb

input:

20 322
3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6
8 14
6 6
3 17
3 16
9 18
7 17
12 13
4 14
12 18
6 13
8 9
3 17
7 20
12 16
10 15
12 16
12 14
16 19
6 7
18 20
6 16
7 14
5 19
12 13
3 14
10 15
11 18
12 20
8 9
1 13
17 18
1 18
4 19
4 9
5 19
4 5
1 2
10 17
11 19
7 14
15 20
20 20
4 7
12 15
7 17
3 13
7 ...

output:

19
0
91
80
37
39
1
48
21
23
1
91
81
10
13
10
3
5
1
2
44
23
87
1
50
13
25
37
1
58
1
119
99
14
87
1
1
21
33
23
15
0
6
7
39
42
36
1
91
3
107
25
1
44
1
0
10
7
1
1
55
3
10
2
34
91
1
51
26
25
75
1
1
18
79
13
1
80
21
16
5
3
0
18
3
7
63
63
66
3
0
5
17
0
21
10
1
3
5
1
6
35
41
29
59
43
21
0
45
3
6
75
1
103
0
...

result:

ok 322 numbers

Test #10:

score: 0
Accepted
time: 1ms
memory: 9956kb

input:

20 1000
16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13
1 6
8 9
9 11
5 18
3 20
2 9
17 18
12 12
12 20
5 17
1 8
10 10
2 9
17 19
1 7
7 15
12 19
2 7
9 14
2 14
1 4
15 17
11 19
2 5
3 12
11 14
11 14
13 17
7 8
9 18
2 11
8 11
1 4
4 8
12 13
12 19
7 16
12 16
11 15
5 9
5 18
2 19
11 15
1 15
4 20
4 9
5 14
5 19...

output:

13
1
3
67
113
21
1
0
34
57
23
0
21
3
19
29
24
15
15
54
5
3
34
7
30
7
7
8
1
39
36
5
5
7
1
24
45
9
9
6
67
113
9
78
95
9
31
76
34
25
78
9
7
9
3
6
21
5
78
55
70
13
51
5
29
9
7
1
14
9
1
3
13
3
94
39
7
4
104
44
17
24
29
85
26
9
49
67
40
5
3
7
65
0
54
76
14
67
7
18
37
7
19
1
5
11
27
21
30
21
7
95
23
15
40
...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 9796kb

input:

20 1000
16 8 20 2 5 9 14 7 19 3 13 1 6 18 10 4 15 17 12 11
9 19
12 12
12 19
15 15
6 17
9 16
1 10
4 19
10 13
11 18
2 7
12 17
18 19
4 15
3 18
3 17
5 11
14 17
4 16
3 13
10 10
12 20
1 1
4 8
3 11
8 15
6 7
9 12
1 16
12 20
2 9
8 9
8 9
8 20
17 18
15 20
11 20
1 3
8 10
2 6
8 18
4 12
7 12
3 18
5 14
14 15
6 10
...

output:

41
0
20
0
53
25
45
91
7
24
13
14
1
63
89
87
21
6
75
51
0
22
0
7
33
29
1
5
101
22
23
1
1
53
1
10
34
3
3
11
43
35
13
89
43
1
7
20
6
33
6
2
1
15
51
41
13
29
1
4
10
51
13
1
16
10
45
19
1
11
3
71
15
22
15
35
87
87
129
23
61
2
33
7
51
0
89
43
3
1
7
71
8
75
7
16
105
19
9
14
43
29
35
33
23
20
29
5
2
3
16
4
...

result:

ok 1000 numbers

Test #12:

score: 0
Accepted
time: 1ms
memory: 10008kb

input:

20 1000
7 16 3 15 5 6 10 20 19 2 13 1 11 4 8 18 12 17 14 9
9 20
17 19
1 13
5 19
18 18
6 8
6 14
3 16
6 16
12 17
9 11
9 20
7 20
3 18
10 13
2 8
6 17
5 7
7 15
3 8
11 13
13 18
6 15
8 18
5 10
6 8
13 20
6 7
10 13
6 20
10 12
12 18
9 12
4 12
16 18
2 5
1 11
3 10
13 18
6 20
2 4
3 8
13 20
17 20
3 13
1 10
1 15
1...

output:

47
3
48
68
0
2
26
82
52
10
3
47
60
94
7
15
60
2
26
11
3
10
42
36
10
2
22
1
7
76
3
12
5
26
3
5
42
20
10
76
3
11
22
6
34
34
82
4
3
11
12
13
1
2
5
1
0
24
16
124
1
9
5
13
90
3
26
6
94
98
86
3
5
14
37
28
38
3
1
30
98
4
0
60
42
0
1
20
6
16
12
1
1
10
11
18
98
24
16
1
4
80
16
26
28
1
124
6
1
40
14
3
16
10
3...

result:

ok 1000 numbers

Test #13:

score: 0
Accepted
time: 1ms
memory: 9784kb

input:

20 1337
10 3 6 8 7 15 4 5 9 19 17 13 1 18 12 16 20 2 11 14
10 14
4 5
9 11
7 14
2 8
7 18
11 18
9 12
2 6
8 15
11 18
12 16
19 19
8 19
12 16
4 11
2 18
1 6
15 19
2 12
4 9
3 5
16 20
10 14
3 9
10 10
7 17
6 11
8 10
3 4
6 18
7 12
1 15
7 16
16 17
3 16
6 12
4 15
10 17
13 19
4 20
18 19
13 14
3 16
8 10
3 16
1 14...

output:

9
1
3
19
16
50
26
5
6
23
26
11
0
56
11
19
84
12
7
34
13
3
7
9
17
0
40
11
2
1
62
7
73
33
1
57
17
43
28
16
94
1
1
57
2
57
67
74
5
5
24
60
4
76
52
3
1
15
9
16
1
19
15
5
2
35
60
5
35
92
22
3
1
0
3
9
6
6
6
73
54
36
9
14
11
17
0
108
73
67
83
4
44
41
14
83
0
3
1
17
64
4
17
17
45
11
3
15
50
23
4
1
30
17
74
...

result:

ok 1337 numbers

Test #14:

score: 0
Accepted
time: 3ms
memory: 15844kb

input:

1000 1000
40 954 881 24 748 110 805 978 860 472 882 621 530 586 488 928 150 443 553 402 177 702 871 214 778 7 489 874 812 754 90 806 206 60 283 243 416 720 650 539 763 588 570 114 658 396 19 970 372 743 587 885 527 296 3 900 313 968 772 280 691 349 37 178 714 49 122 823 143 632 662 387 88 176 400 63...

output:

91858
15668
172586
11352
13480
1
8256
24603
28782
1468
53656
189822
185548
14226
107100
70306
22628
158766
20021
10226
50340
45240
14040
108754
64658
83894
78280
59
145572
421
73592
583
96644
154438
95660
132514
45756
64674
4054
53331
32650
40791
2868
264
53
49416
38470
183908
51910
112924
13670
139...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 6ms
memory: 15700kb

input:

1000 1000
266 949 588 125 665 728 319 483 107 605 86 142 593 228 829 702 298 808 615 575 467 3 548 345 492 859 848 685 265 945 773 440 698 71 743 630 311 834 671 544 927 906 422 614 367 989 923 210 44 856 638 98 636 726 609 76 113 796 565 750 103 196 668 589 278 264 784 998 794 105 354 600 369 931 2...

output:

344
18157
32
669
175
79412
1280
28341
20245
9269
33207
4268
643
5859
40615
71451
25640
32121
65902
2432
11292
65986
19331
226
20819
41463
30009
74575
22
21597
96801
81093
2388
10777
22657
1256
81865
1073
21
166635
51935
33323
55761
489
18242
44795
12578
55349
186681
159317
3224
5235
41753
136129
589...

result:

ok 1000 numbers

Test #16:

score: 0
Accepted
time: 3ms
memory: 15732kb

input:

1000 1000
39 785 629 568 287 13 150 901 702 805 204 362 575 339 843 26 380 291 927 181 9 278 662 876 674 129 794 809 866 442 709 966 644 737 978 283 507 627 525 460 279 375 389 454 369 27 603 121 255 230 528 727 777 589 942 923 145 266 443 249 697 789 812 536 586 391 93 833 267 202 505 956 744 57 39...

output:

58022
164646
252248
24113
712
27872
108362
40237
224150
17438
138258
360
5699
239
15925
205084
2594
55280
6181
71954
25072
79116
10618
34263
373
53596
22330
194978
46786
10422
145746
13962
4838
8935
1291
14694
10340
55920
5263
11863
153
50
65316
2623
9454
151682
242372
4079
6
534
12356
15813
12845
1...

result:

ok 1000 numbers

Test #17:

score: 0
Accepted
time: 0ms
memory: 15764kb

input:

1000 1000
556 686 702 301 252 724 158 296 86 834 162 884 890 448 815 844 974 369 237 411 8 868 353 299 578 527 166 797 141 498 775 997 5 479 732 902 246 244 624 918 376 718 680 990 441 593 234 898 762 339 433 689 233 579 394 938 725 897 455 110 513 362 417 821 477 204 24 747 982 891 925 870 754 271 ...

output:

37802
23905
294066
33720
74794
166792
9370
3169
164940
121220
13
5527
356
113886
53536
153872
29238
264
9289
117314
89842
162068
279608
2635
106
22107
28389
26198
6332
51546
949
15872
307
81238
114314
163594
146270
15078
1009
147878
15076
3283
753
4057
1065
7694
29161
82
1097
13822
57
136566
21204
6...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 15848kb

input:

1000 1000
487 188 387 532 411 790 570 219 22 672 347 510 805 258 736 892 776 840 400 104 227 843 557 407 670 208 574 350 440 163 335 895 369 398 502 46 19 380 18 470 395 293 537 423 235 51 260 538 361 612 905 270 385 645 88 296 733 316 229 847 851 751 978 76 923 699 677 332 841 20 657 15 703 565 169...

output:

4676
12529
10123
121945
51016
50950
35034
9346
20339
11943
900
45
10899
40782
9850
220350
57477
9152
45926
8477
24860
9549
60180
27213
4
14988
241070
27674
14923
126190
67108
42606
98
8136
12274
67838
86
67736
68234
62756
57287
15743
1384
19231
142330
101952
636
266
167380
180794
13093
157492
119534...

result:

ok 1000 numbers

Test #19:

score: 0
Accepted
time: 6ms
memory: 15776kb

input:

1000 1000
832 212 419 284 882 369 312 437 496 937 652 363 659 840 791 572 730 772 416 63 929 302 494 24 61 329 163 241 542 316 341 41 388 164 525 123 472 871 540 222 150 888 82 926 192 249 252 861 761 628 326 465 909 116 842 457 578 487 17 600 998 678 686 187 538 102 243 92 960 788 332 373 923 546 7...

output:

22850
1404
56350
99385
8530
111263
112429
110327
30307
84285
175189
8278
36519
15670
22393
23394
49964
70090
18303
12420
17887
64227
128351
4461
88687
36231
124735
197623
190541
190695
19010
1298
256333
12395
39703
75101
5953
2030
6329
21387
87957
19535
158807
1888
1385
6442
153793
23755
460
17138
2...

result:

ok 1000 numbers

Test #20:

score: 0
Accepted
time: 6ms
memory: 15760kb

input:

1000 1000
985 117 995 842 388 526 509 668 773 738 926 747 166 466 114 983 597 89 124 230 818 441 178 211 43 325 858 584 843 456 240 486 674 313 315 719 550 400 323 9 264 29 414 277 96 734 238 152 554 207 170 363 428 488 537 492 596 618 778 279 721 735 222 941 236 736 866 63 485 258 540 110 434 856 3...

output:

78364
52364
127886
984
1555
36880
292085
65
9337
54109
2194
169387
15385
162293
149983
588
148333
176831
62758
24026
65099
160561
21377
55331
100
11041
74818
78045
2443
19645
22600
89582
49978
235011
604
221613
110101
168307
126573
65932
4240
240537
28833
216487
15865
121457
5327
70546
13277
5013
16...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 6ms
memory: 13724kb

input:

1000 1000
585 437 432 207 862 723 368 485 692 687 607 385 612 981 182 405 162 912 502 573 765 963 801 104 451 440 718 238 512 817 246 748 516 184 250 105 550 902 174 760 242 285 237 14 764 997 617 533 777 519 675 968 154 462 987 172 126 740 436 549 133 706 12 962 587 209 887 508 903 328 76 653 298 3...

output:

428
6340
1658
4990
27629
21897
152237
190416
43389
33458
365
64021
18
105531
175631
88041
71001
12446
4520
109267
139681
122035
0
28288
64555
10643
1994
53
109231
120
43461
67
190039
237
9856
547
26351
38487
13923
43427
93
72701
170
9482
12064
119105
9575
649
133545
38902
19291
28461
69723
724
648
1...

result:

ok 1000 numbers

Test #22:

score: 0
Accepted
time: 3ms
memory: 15704kb

input:

1000 1000
535 890 985 726 493 294 827 348 250 400 758 698 84 243 142 811 680 805 952 297 335 784 760 17 447 18 488 286 767 525 212 971 104 775 694 843 95 506 23 117 12 771 374 420 432 140 616 738 56 823 824 559 276 7 115 82 610 599 320 251 794 943 347 232 615 342 705 978 875 167 576 434 515 643 458 ...

output:

258109
55439
41347
29936
91129
1529
91323
0
161331
223171
2917
16836
81743
225387
271315
28686
20794
3786
24712
24049
6905
9086
1344
4945
20776
5580
5095
732
69374
2811
34365
2043
3277
32030
1
544
127699
37369
3466
230729
287399
1
5041
38025
53061
53961
2812
33811
117566
53223
24615
6645
75499
11541...

result:

ok 1000 numbers

Test #23:

score: 0
Accepted
time: 0ms
memory: 15776kb

input:

1000 1000
236 440 985 779 964 945 839 771 524 695 477 845 346 812 552 856 39 200 948 374 232 504 673 259 635 880 678 610 623 768 202 910 352 711 865 54 125 594 276 243 405 940 120 656 14 268 821 707 776 723 664 380 441 912 971 873 788 181 770 287 568 835 166 483 112 944 973 591 283 460 725 480 647 7...

output:

55099
20190
170519
95335
14104
3522
190007
38812
109137
99788
19130
785
241870
40435
2248
216604
21665
72449
157958
12958
74023
4517
28642
7299
5707
756
19499
121185
15779
69094
84017
398
224
38611
35520
53167
6
20679
6335
16415
115144
47122
55140
30903
107943
124467
21753
829
4842
130348
87613
2720...

result:

ok 1000 numbers

Test #24:

score: 0
Accepted
time: 626ms
memory: 317876kb

input:

100000 100000
99697 62499 65369 38767 49004 41714 25240 40929 74271 97963 88205 44238 73947 88038 34453 94958 48075 26199 66549 43887 35818 48583 77453 8018 7436 18980 53885 59267 27907 86681 21554 51609 87147 5287 55193 67166 40294 1148 10152 60727 50341 38377 11343 17679 59993 52512 5533 6531 8363...

output:

1288074471
1865519129
582493609
1276924537
3161681147
129374494
54414043
1267409015
234290573
187149742
261317634
317082635
539993333
829166
156613675
2059481141
108499906
1312589341
96309609
468984063
12524390
892745811
1283743683
461204445
86654104
79621536
890662789
299705283
1097531521
174275952...

result:

ok 100000 numbers

Test #25:

score: 0
Accepted
time: 895ms
memory: 320252kb

input:

100000 200000
47901 40509 82712 65176 65242 38059 52717 8412 8309 57296 31699 55303 93246 95583 64025 63028 40895 19747 77421 42608 75427 38707 99837 71066 12552 13047 29149 44233 89395 78799 72754 24013 48868 40 71281 75385 42374 14591 25627 69889 73415 33560 28871 37847 1663 83908 415 60511 94235 ...

output:

1071809911
218494195
78075942
73965
1542335901
7069757
5019064
293992977
34007786
2042099097
550516487
1860127303
387805746
13031549
2060342321
341150655
23146333
438484238
16513142
48670538
14618462
49683502
2120709
79812253
1371892427
821871224
347164739
6277885
30486942
654389751
541793597
180450...

result:

ok 200000 numbers

Test #26:

score: 0
Accepted
time: 1133ms
memory: 322520kb

input:

100000 300000
14145 3095 96177 71633 83992 70489 79692 70842 64134 50933 7786 75764 44663 11407 14283 40703 47857 59376 76060 43783 90342 47520 16645 60656 30223 39789 21248 66886 72240 39601 7470 77023 54835 61681 15121 99842 53250 53656 35668 76792 1805 99204 95988 77282 4639 22945 61929 16984 969...

output:

214410630
215182022
89863953
54003262
98105232
454087256
338036716
183032284
1127073540
566146170
5615850
266308348
486483724
1490483866
91138470
32159258
7830846
491330544
353886208
2920450946
11553365
1612357842
421925556
434047846
323606938
125400
2079805154
128865548
701223932
65278535
6866891
3...

result:

ok 300000 numbers

Test #27:

score: 0
Accepted
time: 1392ms
memory: 324568kb

input:

100000 400000
10449 40807 78248 39718 95023 74938 29946 22021 83905 56250 73479 95338 64292 36543 48899 43900 95785 39120 70372 81155 85778 84896 65784 66472 94472 40683 79945 73211 6509 5275 49587 79722 1246 25889 30001 95895 85147 31931 59915 28113 80959 91735 11613 15677 18681 64369 19498 64864 5...

output:

44921232
47098787
170643635
1876450520
971907286
10123755
1565988498
380882251
133023719
881501806
139398165
445730470
545882260
502042537
2301026650
722283056
812109926
77500223
44978699
54322571
63883517
190123896
3000824158
58234557
1342255720
29060700
698688304
231543499
108149094
113054070
3098...

result:

ok 400000 numbers

Test #28:

score: 0
Accepted
time: 1637ms
memory: 326600kb

input:

100000 500000
9965 82716 93502 59687 36792 48844 97065 58196 84155 7434 80866 95386 44473 57161 70219 74805 67966 91664 39565 73809 34170 62596 81682 62342 35414 60448 52444 7830 76648 45978 11969 80785 98099 64428 33700 18905 45899 92153 72746 99958 77646 67579 23888 70394 60211 747 42666 43364 558...

output:

45099523
4100229
752253187
948959293
290181809
70706758
634066898
136004775
33398227
297654
66661483
195896218
7031612
449005758
10177036
678129016
445424686
51080088
5189338
91482
314717082
1152347043
2606448057
943610289
71253067
1154735755
148368578
193579360
879554051
307691803
30567438
25885256...

result:

ok 500000 numbers

Test #29:

score: 0
Accepted
time: 1676ms
memory: 326596kb

input:

100000 500000
26129 70585 92281 58101 85008 44535 43523 31457 91981 58653 26571 63197 14406 76873 46752 53212 61661 69021 73723 44909 67786 10222 56048 61247 40918 50102 65797 20039 83188 78415 69606 87766 97231 4886 58292 91292 94415 46858 51808 73003 95891 86168 79403 55603 81025 54822 70873 7549 ...

output:

17367008
471259084
213987102
443296685
133382948
817588686
1878100
188811526
7863643
179932479
2446866
160405752
1051044990
916736622
116118036
438617708
1608727912
19943685
1340452408
33318870
16545211
673784712
173604123
587431179
13266807
21714259
5097491
1175192606
2085062566
4601876
1031533197
...

result:

ok 500000 numbers

Test #30:

score: 0
Accepted
time: 1654ms
memory: 326596kb

input:

100000 500000
91490 75135 74930 92306 69823 86998 43651 25466 94874 66627 87972 72264 72362 56034 15168 54374 73119 43688 84320 67433 95192 52687 11740 57744 85791 34601 19787 55409 17605 62548 89976 80912 10260 46263 73699 7903 27824 34493 3660 46171 61481 16295 56910 90471 8792 94926 22137 7856 45...

output:

29554978
1837907443
110336110
448230571
475953560
159559243
2941100757
1363481207
517650509
2996507
1977735937
749685827
5189039
19040118
1502960203
1895600509
630406700
30923148
564462355
10623780
1395159265
556203529
69764674
169034031
319337715
313520158
18519650
162124615
88730934
24216821
38401...

result:

ok 500000 numbers

Test #31:

score: 0
Accepted
time: 1741ms
memory: 326452kb

input:

100000 500000
62347 92838 79967 45228 86962 95077 12699 29707 30211 9341 97296 9612 42588 20816 26368 63185 4833 99291 84850 2162 18188 95360 58703 62214 35484 98197 50981 73229 29544 69963 8352 62402 966 9770 76804 96648 55469 5994 81556 99675 79099 42427 14321 97856 88264 26135 82786 46696 19660 1...

output:

7867740
2083270
123669993
1456656625
289487511
731628881
2614261328
947414841
3014207080
103196923
5116250
1453520981
1257952648
215499023
142784971
81488801
142787483
39349355
1467848564
2854448289
110994716
40490710
115420397
2885895
282126475
104842837
876271037
785850167
33962045
447978597
68931...

result:

ok 500000 numbers

Test #32:

score: 0
Accepted
time: 1684ms
memory: 326612kb

input:

100000 500000
45007 78357 47246 71015 78432 37891 75777 23275 84620 6951 65573 41045 13984 35520 95959 78528 98837 81120 12567 68384 72343 91076 14572 69407 25352 48747 2691 21879 68218 50116 46980 66304 91981 42711 15330 12361 64333 56493 385 94843 23470 66781 88619 47458 38197 18423 66176 21549 74...

output:

116600994
239947437
795958205
70769372
621999263
865793297
9909851
164856533
358692820
1752458355
1189091783
1010863549
638553237
398000054
552674597
23317331
917359115
104780505
365060534
399723197
28416203
2465522
290139158
937207641
833003407
222007977
231912569
241141067
136830905
939109723
5536...

result:

ok 500000 numbers

Test #33:

score: 0
Accepted
time: 1669ms
memory: 326656kb

input:

100000 500000
46194 44726 15431 47379 51288 67079 96317 16078 94888 71366 98374 40752 75290 55586 88129 15082 24095 10645 6828 41028 25099 98523 86174 60718 86901 38444 10993 86748 76314 63238 5836 52159 21518 70563 88150 2430 52848 17322 27223 52840 56240 39068 25371 98026 47869 98981 10669 25611 5...

output:

194855801
677245482
2930608664
1133334916
479301976
65745081
782147376
998353078
119563515
55207793
253800927
2046743790
1133760018
378142700
561895423
863372838
164451647
3767728
909805442
666753122
45321665
110800533
2672902046
223940931
688404834
132510713
494102349
14184281
76848723
613396251
92...

result:

ok 500000 numbers

Test #34:

score: 0
Accepted
time: 1ms
memory: 9636kb

input:

20 5
18 3 5 2 17 11 9 13 14 20 7 1 6 8 10 4 19 16 12 15
8 16
3 19
13 20
2 2
12 16

output:

22
138
13
0
9

result:

ok 5 number(s): "22 138 13 0 9"

Test #35:

score: 0
Accepted
time: 1153ms
memory: 326944kb

input:

100000 500000
11355 21171 23744 95348 95644 71235 19958 92268 25078 97198 99149 30559 90201 83697 32042 70376 20689 14872 77054 65856 77740 73228 25931 69930 87443 56036 48045 76249 8462 11337 94613 7925 90720 30780 6819 14901 22724 92776 80464 46270 78101 48353 70964 49049 58814 8468 18805 63726 69...

output:

11171
2486
16907
6437
21259
8511
25925
11853
38323
17137
39901
27725
62745
34707
66695
47429
94377
60373
100145
62583
104551
67293
109509
116613
179543
131251
194637
180673
261589
210134
307612
266660
374530
295348
400552
312248
408092
343060
454216
363436
467742
377836
505202
415450
522802
432322
5...

result:

ok 500000 numbers

Test #36:

score: 0
Accepted
time: 1167ms
memory: 326944kb

input:

100000 500000
23718 14300 35450 86483 27316 48032 42859 53053 51314 25679 27661 11933 13124 79103 10783 76344 25479 97918 82049 29909 65545 78458 78952 62386 28014 15210 63982 11259 67766 10636 75027 40901 30185 20794 30353 86166 7416 86310 67426 10711 22832 19079 5038 56729 99206 20730 55483 15738 ...

output:

5269
433
7917
887
12597
2222
13039
5953
24963
7781
37621
19151
42589
20795
55015
31546
71500
50190
88856
56712
112919
82549
121251
86219
151255
115217
196517
150111
216597
167481
223609
188667
255045
247577
329591
264169
352225
295223
380607
300779
423723
342849
439069
362291
460583
375825
499453
53...

result:

ok 500000 numbers

Test #37:

score: 0
Accepted
time: 1140ms
memory: 326604kb

input:

100000 500000
82664 86387 42899 69662 76953 26380 92353 61030 42361 21492 31492 67630 21609 12245 3323 59718 80796 89481 42376 43453 8136 23796 18550 625 15127 87735 31025 50707 74139 2277 77593 27396 23457 53492 70082 29081 49918 85747 56707 76852 33412 35601 95179 24710 37887 95489 18677 7880 5118...

output:

5926
231
9684
791
10798
2607
15864
5783
29933
14479
41803
20587
49549
29591
83377
57685
97607
65621
104613
71349
188425
133161
195587
149123
240183
181961
254537
185881
268707
236321
349131
273321
377587
353743
442827
355185
493751
420940
536824
480282
586440
553954
671392
576968
756434
640862
85598...

result:

ok 500000 numbers

Test #38:

score: 0
Accepted
time: 1171ms
memory: 326680kb

input:

100000 500000
51483 98105 27901 12500 80766 74002 26454 51358 71894 80996 6380 33361 66179 76871 9804 13922 35080 96324 44134 30903 40288 48733 48899 80961 65926 73137 50893 64888 33071 16305 25509 61221 3670 58966 70261 10858 70993 12591 74173 39105 33899 12193 29973 50328 18496 89014 91150 35200 6...

output:

9502
824
11243
1968
19605
4466
26477
7802
32937
27886
69237
46760
99317
61668
119917
82032
148235
100598
170016
118175
176976
137489
227100
158529
231356
169001
242726
177913
272972
201343
300754
223915
315676
254065
345912
263601
383532
303637
402554
314271
409284
367571
469466
376887
502184
399317...

result:

ok 500000 numbers

Test #39:

score: 0
Accepted
time: 1193ms
memory: 326608kb

input:

100000 500000
51217 5221 8247 78730 35744 79377 36094 65689 35332 7451 77376 76618 79277 99407 92213 28936 56658 62076 62648 6677 98211 63170 37220 49008 82545 17988 59019 23064 12187 35517 30148 85242 22114 24867 46838 32551 9566 86347 96308 60508 16413 89738 67299 36201 62825 23537 93653 96911 905...

output:

8836
2501
30959
17594
43889
27390
61821
45609
95186
56162
110654
64332
132750
80714
142308
94762
156114
109268
179350
132334
205774
152057
227425
176945
287087
224075
313261
233131
335979
256985
357817
275619
397711
327469
440809
359309
460089
375749
540832
440178
556488
464308
583042
530636
765474
...

result:

ok 500000 numbers

Test #40:

score: 0
Accepted
time: 1179ms
memory: 326540kb

input:

100000 500000
93251 91786 75460 56752 97539 16167 41079 49543 10036 25123 82422 95406 93458 51092 54219 70546 93153 8174 70129 78087 82706 22710 125 50341 12896 90869 90389 7074 33427 31203 72346 37513 43371 83784 89759 96902 14257 64897 52144 10489 95263 62853 66165 48604 30082 79626 44042 98567 85...

output:

11824
1693
15830
1983
16884
3065
19500
21367
52443
26919
75629
39983
139203
91516
158030
105756
178434
117286
222026
168032
271414
201416
315584
224266
324684
231488
358630
280282
391122
290588
401038
322260
432700
360224
480232
500370
618496
518690
668339
560709
731237
612095
780093
676333
842671
7...

result:

ok 500000 numbers

Test #41:

score: 0
Accepted
time: 1198ms
memory: 326676kb

input:

100000 500000
74548 14903 75490 94676 6498 18048 91146 53810 73539 45616 21225 61594 58027 34157 81379 97128 42885 58313 88841 40738 50467 25877 77813 68938 98323 47438 22364 20154 49129 50987 98564 35405 54790 74507 318 66585 43311 82677 48117 4369 99072 21712 54561 81337 93542 52918 40850 58377 88...

output:

7508
2951
25710
19786
64244
30352
80662
41698
84616
48084
112094
70069
121490
70103
122244
71481
129830
95921
167230
117139
211860
163250
306566
239168
346310
272376
403430
293408
428725
320955
446309
335401
497659
514411
658865
544649
725985
694461
878189
758041
1016666
883062
1125230
989860
117117...

result:

ok 500000 numbers

Test #42:

score: 0
Accepted
time: 1205ms
memory: 326600kb

input:

100000 500000
61045 89545 7703 18657 97237 35067 59645 72924 26365 93662 22927 4954 23196 6032 26410 91524 13305 57059 32545 98400 22047 27843 32168 20167 2419 72312 42570 17587 149 63838 91451 38903 52054 14595 52346 57236 53206 99997 94137 74666 5924 46112 12302 28683 95033 56422 41757 93384 95668...

output:

12543
3676
41006
15889
52318
28913
67486
36313
85996
50315
103548
59721
104690
59543
117148
69155
126824
83231
192084
142251
212922
157845
257142
203237
297294
218457
320936
235453
396208
294289
401984
313791
426906
416409
533032
445921
567542
500547
690038
574747
806676
739183
883186
806245
1021860...

result:

ok 500000 numbers

Test #43:

score: 0
Accepted
time: 1209ms
memory: 326508kb

input:

100000 500000
58884 47530 93822 91915 95896 30865 74180 67259 18756 15686 94148 87414 91737 52044 79164 19996 4081 36732 64483 51076 31544 50767 14739 76756 65174 91540 13265 56710 64534 14557 95898 11320 78075 72896 19115 3575 40837 84954 36205 17384 734 99751 33693 19751 23456 24725 11170 46766 53...

output:

10836
201
11688
424
28832
7000
33782
12792
43784
21304
56202
23476
66946
30542
82786
54368
107960
67398
125016
70684
135434
79236
141912
82998
151484
107140
173662
109588
216428
156608
237470
202130
337630
253824
426248
324916
431272
326558
480402
382338
544084
461549
647252
553699
692212
653663
848...

result:

ok 500000 numbers
English 繁體中文 简体中文

伺服器時間: 2024-11-30 00:43:01 | 開源專案