QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#640313	#8889. Ice Cream Machines	Bucketsmith	100 ✓	35ms	8492kb	C++20	1.1kb	2024-10-14 10:55:10	2024-10-14 10:55:12

Judging History

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

[2024-10-14 10:55:12]
评测

测评结果：100
用时：35ms
内存：8492kb

查看

[2024-10-14 10:55:10]
提交

answer

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int N = 1 << 18;

int n, m, k;

int a[N], nxt[N], b[N];

int tr[N * 2];

void update(int p, int x) {
    tr[N + p] = x;
    for(int i = (N + p) / 2; i; i /= 2)
        tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
}

void popMax() {
    int i = 1;
    while(i < N) {
        i *= 2;
        if(tr[i] < tr[i + 1]) i ++;
    }
    update(i - N, 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    
    fill(nxt + 1, nxt + m + 1, n + 1);

    for(int i = n; i >= 1; i --) {
        b[i] = nxt[a[i]];
        nxt[a[i]] = i;
    }

    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        if(tr[N + a[i]]) {
            update(a[i], b[i]);
            continue;
        }
        if(k > 0) {
            update(a[i], b[i]);
            k --;
            ans ++;
            continue;
        }
        ans ++;
        popMax();
        update(a[i], b[i]);
    }
    cout << ans << "\n";
}

源文件, 语言: C++20

详细

Subtask #1:

score: 7

Accepted

Test #1:

score: 7

Accepted

time: 1ms

memory: 5804kb

input:

output:

result:

ok 1 number(s): "899"

Test #2:

score: 7

Accepted

time: 1ms

memory: 5652kb

input:

output:

result:

ok 1 number(s): "1"

Test #3:

score: 7

Accepted

time: 1ms

memory: 7732kb

input:

output:

result:

ok 1 number(s): "655"

Test #4:

score: 7

Accepted

time: 1ms

memory: 5664kb

input:

output:

result:

ok 1 number(s): "565"

Test #5:

score: 7

Accepted

time: 1ms

memory: 7684kb

input:

output:

result:

ok 1 number(s): "599"

Test #6:

score: 7

Accepted

time: 1ms

memory: 7812kb

input:

output:

result:

ok 1 number(s): "731"

Test #7:

score: 7

Accepted

time: 1ms

memory: 5652kb

input:

output:

result:

ok 1 number(s): "1000"

Subtask #2:

score: 12

Accepted

Dependency #1:

100%

Accepted

Test #8:

score: 12

Accepted

time: 1ms

memory: 5708kb

input:

output:

result:

ok 1 number(s): "629"

Test #9:

score: 12

Accepted

time: 0ms

memory: 7684kb

input:

output:

result:

ok 1 number(s): "2"

Test #10:

score: 12

Accepted

time: 0ms

memory: 7748kb

input:

output:

result:

ok 1 number(s): "556"

Test #11:

score: 12

Accepted

time: 0ms

memory: 5732kb

input:

output:

result:

ok 1 number(s): "25"

Test #12:

score: 12

Accepted

time: 0ms

memory: 7688kb

input:

output:

result:

ok 1 number(s): "374"

Test #13:

score: 12

Accepted

time: 0ms

memory: 7748kb

input:

output:

result:

ok 1 number(s): "472"

Test #14:

score: 12

Accepted

time: 0ms

memory: 7684kb

input:

output:

result:

ok 1 number(s): "890"

Subtask #3:

score: 22

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #15:

score: 22

Accepted

time: 1ms

memory: 5672kb

input:

output:

result:

ok 1 number(s): "284"

Test #16:

score: 22

Accepted

time: 1ms

memory: 7744kb

input:

output:

result:

ok 1 number(s): "5"

Test #17:

score: 22

Accepted

time: 0ms

memory: 7760kb

input:

output:

result:

ok 1 number(s): "269"

Test #18:

score: 22

Accepted

time: 1ms

memory: 5732kb

input:

output:

result:

ok 1 number(s): "64"

Test #19:

score: 22

Accepted

time: 1ms

memory: 7840kb

input:

output:

result:

ok 1 number(s): "222"

Test #20:

score: 22

Accepted

time: 1ms

memory: 7772kb

input:

output:

result:

ok 1 number(s): "169"

Test #21:

score: 22

Accepted

time: 0ms

memory: 5800kb

input:

output:

result:

ok 1 number(s): "5"

Test #22:

score: 22

Accepted

time: 1ms

memory: 5720kb

input:

output:

result:

ok 1 number(s): "2"

Test #23:

score: 22

Accepted

time: 1ms

memory: 7748kb

input:

output:

result:

ok 1 number(s): "560"

Subtask #4:

score: 11

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #24:

score: 11

Accepted

time: 1ms

memory: 7624kb

input:

1000 200 100
125
25
197
45
187
19
77
114
143
176
87
180
3
10
92
95
22
170
50
133
76
157
200
144
73
185
127
140
133
29
40
39
54
166
56
76
151
200
188
9
60
199
112
28
188
87
68
100
74
85
60
68
187
5
105
1
35
198
150
150
24
148
14
40
159
173
25
181
176
88
138
42
78
51
130
190
180
19
127
98
28
172
135
1...

output:

result:

ok 1 number(s): "290"

Test #25:

score: 11

Accepted

time: 1ms

memory: 5780kb

input:

1000 100 100
58
27
79
62
81
57
46
85
12
57
28
70
74
8
77
5
11
45
52
14
79
34
49
35
22
94
92
94
12
69
61
90
13
63
90
87
88
73
6
88
38
31
21
13
75
2
95
88
47
13
74
14
84
40
96
69
74
48
63
1
61
51
43
39
27
4
98
34
69
22
76
26
19
67
28
96
73
64
77
52
23
42
31
40
89
88
69
1
63
59
66
75
2
26
2
63
73
11
22...

output:

result:

ok 1 number(s): "100"

Test #26:

score: 11

Accepted

time: 1ms

memory: 5640kb

input:

output:

result:

ok 1 number(s): "155"

Test #27:

score: 11

Accepted

time: 1ms

memory: 5704kb

input:

output:

result:

ok 1 number(s): "489"

Test #28:

score: 11

Accepted

time: 1ms

memory: 5648kb

input:

output:

result:

ok 1 number(s): "12"

Test #29:

score: 11

Accepted

time: 1ms

memory: 7748kb

input:

output:

result:

ok 1 number(s): "134"

Test #30:

score: 11

Accepted

time: 1ms

memory: 5740kb

input:

output:

result:

ok 1 number(s): "748"

Test #31:

score: 11

Accepted

time: 1ms

memory: 5708kb

input:

output:

result:

ok 1 number(s): "37"

Test #32:

score: 11

Accepted

time: 1ms

memory: 7816kb

input:

output:

result:

ok 1 number(s): "335"

Test #33:

score: 11

Accepted

time: 1ms

memory: 5648kb

input:

output:

result:

ok 1 number(s): "50"

Test #34:

score: 11

Accepted

time: 1ms

memory: 5656kb

input:

1000 100 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99...

output:

result:

ok 1 number(s): "100"

Test #35:

score: 11

Accepted

time: 0ms

memory: 5652kb

input:

output:

result:

ok 1 number(s): "10"

Test #36:

score: 11

Accepted

time: 0ms

memory: 7688kb

input:

1000 200 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99...

output:

result:

ok 1 number(s): "600"

Subtask #5:

score: 14

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Test #37:

score: 14

Accepted

time: 24ms

memory: 6504kb

input:

200000 500 100
99
80
424
158
170
220
376
198
250
362
228
479
37
82
321
63
455
101
442
406
44
297
300
66
17
321
229
260
35
375
344
292
214
413
271
246
252
287
327
161
246
136
371
491
324
76
443
373
336
218
307
431
483
38
392
6
134
116
320
137
480
19
268
196
368
165
207
63
287
134
448
121
490
438
436
...

output:

result:

ok 1 number(s): "91181"

Test #38:

score: 14

Accepted

time: 13ms

memory: 6528kb

input:

200000 100 100
32
89
50
34
87
52
55
20
43
2
16
97
33
20
68
19
12
84
2
61
45
93
20
27
43
3
18
62
76
10
57
11
29
91
25
91
35
27
98
96
20
1
17
31
6
43
65
18
87
17
36
63
73
5
24
18
15
63
47
10
58
65
49
36
21
90
3
37
51
42
79
47
9
83
61
88
1
20
54
35
78
10
91
83
57
61
14
10
84
42
86
30
62
31
83
77
76
62
...

output:

result:

ok 1 number(s): "100"

Test #39:

score: 14

Accepted

time: 13ms

memory: 6344kb

input:

177460 25 99
24
9
11
17
14
9
22
14
12
6
1
14
22
14
18
16
7
18
2
13
2
11
23
4
24
10
18
20
4
15
4
17
16
22
18
21
21
18
25
18
21
6
17
4
13
1
4
12
6
4
2
15
5
7
23
19
6
10
17
11
4
22
13
15
18
5
22
24
17
11
7
5
11
2
5
8
13
7
23
3
19
17
2
19
9
8
16
12
6
21
6
16
4
23
23
25
5
1
18
16
8
17
9
1
7
20
6
16
17
19...

output:

result:

ok 1 number(s): "25"

Test #40:

score: 14

Accepted

time: 1ms

memory: 5676kb

input:

output:

result:

ok 1 number(s): "983"

Test #41:

score: 14

Accepted

time: 16ms

memory: 7712kb

input:

149219 477 47
239
170
53
160
199
389
69
278
295
119
449
55
76
244
109
74
400
445
369
444
315
272
414
22
64
40
226
8
31
269
277
313
14
469
68
53
398
325
218
239
351
367
91
114
243
470
245
346
282
152
434
6
463
375
296
154
291
159
234
87
164
204
346
308
178
409
392
117
15
354
127
451
279
230
42
416
40...

output:

result:

ok 1 number(s): "91551"

Test #42:

score: 14

Accepted

time: 14ms

memory: 6580kb

input:

200000 100 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

output:

result:

ok 1 number(s): "100"

Test #43:

score: 14

Accepted

time: 13ms

memory: 8072kb

input:

output:

result:

ok 1 number(s): "5"

Test #44:

score: 14

Accepted

time: 28ms

memory: 8308kb

input:

200000 500 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
...

output:

result:

ok 1 number(s): "160400"

Subtask #6:

score: 13

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Test #45:

score: 13

Accepted

time: 35ms

memory: 8456kb

input:

200000 200000 100
196573
21699
98897
136926
155446
60763
37617
187437
21625
118328
173949
62775
79535
19024
67639
34999
117913
104597
165320
24791
173932
22180
178078
189656
56674
155939
158942
190736
5013
46872
147194
77696
37539
90076
148830
67233
120958
181419
152627
28133
105919
181499
57461
864...

output:

result:

ok 1 number(s): "194104"

Test #46:

score: 13

Accepted

time: 10ms

memory: 8148kb

input:

55452 88599 39
39654
64978
42880
34032
82563
8103
1035
21159
68462
25953
10130
41172
6665
29173
36674
10409
13183
46267
6874
41351
13804
6225
22345
37010
15843
75101
55028
39550
2429
82229
37165
4980
61938
38250
5760
39449
56696
80370
4048
27966
61871
67327
84793
54367
39747
32710
31225
86379
67142
...

output:

result:

ok 1 number(s): "53991"

Test #47:

score: 13

Accepted

time: 33ms

memory: 7344kb

input:

192448 103997 33
102423
39451
99430
11837
5144
91976
91226
88842
51836
9577
99789
49293
15413
88735
57937
39489
57234
20663
6910
27112
57618
95208
26203
100903
61771
48364
92173
35532
20744
81160
102359
57318
32225
68617
53758
83961
3953
17039
15667
96753
64733
15752
46661
66679
38655
42974
37206
29...

output:

result:

ok 1 number(s): "188189"

Test #48:

score: 13

Accepted

time: 29ms

memory: 7632kb

input:

163176 162224 93
121333
109850
110740
122659
49175
29335
117642
26192
147076
46572
48070
150479
71464
30134
94631
23569
2679
32344
40926
98608
98133
71571
134735
73922
65386
34202
108799
97374
143754
31185
129710
60507
59644
3696
2408
129016
145103
52687
114655
40121
58418
5819
152241
153330
108612
...

output:

result:

ok 1 number(s): "158051"

Test #49:

score: 13

Accepted

time: 34ms

memory: 7432kb

input:

198282 124345 37
76013
37311
78700
68130
73977
47093
10140
57363
4011
979
14040
34667
6757
80257
25428
48202
35719
59171
76761
106557
18931
91928
65948
105129
121507
107251
11796
95987
67452
58635
74664
25343
65763
43595
113433
98573
72731
6074
21926
101761
108448
117912
121590
122856
103969
78035
1...

output:

result:

ok 1 number(s): "193851"

Test #50:

score: 13

Accepted

time: 30ms

memory: 8104kb

input:

200000 200000 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
...

output:

result:

ok 1 number(s): "200000"

Test #51:

score: 13

Accepted

time: 32ms

memory: 6568kb

input:

200000 10000 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
9...

output:

result:

ok 1 number(s): "198100"

Subtask #7:

score: 21

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

100%

Accepted

Dependency #5:

100%

Accepted

Dependency #6:

100%

Accepted

Test #52:

score: 21

Accepted

time: 19ms

memory: 8328kb

input:

200000 200000 199999
23913
28400
53657
152656
94059
60844
81000
168423
119878
180076
29911
30815
175115
190250
56567
62942
62422
173007
147805
195392
98066
149771
138704
64924
94632
115019
199401
96546
2966
45044
53815
134047
135497
102436
115683
139532
174336
62747
178525
78391
94866
146101
164788
...

output:

result:

ok 1 number(s): "126430"

Test #53:

score: 21

Accepted

time: 18ms

memory: 8492kb

input:

200000 200000 200000
65754
141632
64816
143651
169410
76331
50458
126744
115890
50005
11132
158101
43198
96262
122960
19112
144482
121736
88239
131492
174046
131149
69417
48898
162017
77919
152557
31696
2684
10251
61335
8654
45092
56940
182269
29414
39720
106672
157072
34891
165702
167741
59966
1186...

output:

result:

ok 1 number(s): "126586"

Test #54:

score: 21

Accepted

time: 4ms

memory: 7992kb

input:

39264 74648 183450
34417
22759
55340
23134
64664
42888
48335
65725
68197
6559
37735
31717
1357
30617
61263
66218
65548
25576
31603
44591
18046
11566
9286
37288
14943
51569
2143
50085
4208
29017
33461
25581
27025
54648
62976
33357
55555
54895
45419
6938
30070
35987
11746
37241
52934
13605
30574
1825
...

output:

result:

ok 1 number(s): "30584"

Test #55:

score: 21

Accepted

time: 18ms

memory: 7860kb

input:

187035 184169 145590
173529
35096
170294
19480
51071
47289
118281
100884
156835
88710
71642
4460
118389
169341
63572
50502
24746
96179
27330
127347
45983
82087
75295
44463
39372
128547
147203
149833
74693
171585
109490
108987
59777
87025
136480
106067
129460
16428
1133
181001
151212
79685
5162
14485...

output:

result:

ok 1 number(s): "117465"

Test #56:

score: 21

Accepted

time: 13ms

memory: 8172kb

input:

159111 26352 147881
8955
11011
26219
20246
2040
20119
446
595
3271
16008
2973
21951
23040
22745
24310
21251
11600
20163
3471
24862
4639
12436
341
8617
11391
2243
7522
701
23997
2249
10966
7082
12778
19783
7081
17275
18609
5489
18504
19101
9839
10717
15128
14853
17387
2052
9844
6534
20598
22815
10280...

output:

result:

ok 1 number(s): "26295"

Test #57:

score: 21

Accepted

time: 15ms

memory: 6652kb

input:

200000 10000 10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97...

output:

result:

ok 1 number(s): "10000"

Test #58:

score: 21

Accepted

time: 21ms

memory: 8060kb

input:

200000 200000 100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
...

output:

result:

ok 1 number(s): "200000"

Test #59:

score: 21

Accepted

time: 23ms

memory: 6560kb

input:

200000 10000 5000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
...

output:

result:

ok 1 number(s): "105000"

Extra Test:

score: 0

Extra Test Passed