QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#567357#9313. Make MaxKelvin_LAC ✓54ms12308kbC++141.0kb2024-09-16 11:21:102024-09-18 15:57:37

Judging History

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

  • [2024-09-18 15:57:37]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:54ms
  • 内存:12308kb
  • [2024-09-18 15:56:24]
  • hack成功,自动添加数据
  • (/hack/836)
  • [2024-09-16 11:21:11]
  • 评测
  • 测评结果:100
  • 用时:55ms
  • 内存:12908kb
  • [2024-09-16 11:21:10]
  • 提交

answer

#include <iostream>
#include <bitset>
#include <algorithm>
using namespace std;
const int N = 4e5 + 7;
int L[N], R[N];
bitset<N> vis;
struct Node { int x, c; } a[N], v[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vis.reset();
		int m = 0;
		for (int i = 1, x; i <= n; ++i) {
			cin >> x;
			if (x == v[m].x) ++v[m].c;
			else a[++m] = {x, m}, v[m] = {x, 1}, vis[m] = 1;
			L[i] = i - 1, R[i] = i + 1;
		}
		sort(a+1, a+m+1, [](Node &x, Node &y) { 
			return x.x<y.x || (x.x==y.x && x.c<y.c); 
		});
		long long ct = 0;
		for (int i = 1; i < m; ++i) {
			int id = a[i].c, l = L[id], r = R[id];
			if (!vis[id]) continue;
			L[r] = l, R[l] = r, vis[id] = 0;
			if (!l && r>m) break;
			if ((l && v[l].x<v[r].x) || r>m)
				v[l].c += v[id].c;
			else if (v[l].x==v[r].x) {
				v[l].c += v[id].c + v[r].c, vis[r] = 0;
				r = R[r], L[r] = l, R[l] = r; 
			} else if (r <= m) v[r].c += v[id].c;
			ct += v[id].c;
		}
		cout << ct << "\n";
	}
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

4
2
1 2
2
2 2
7
1 1 1 2 2 2 2
3
1 2 3

output:

1
0
3
3

result:

ok 4 number(s): "1 0 3 3"

Test #2:

score: 0
Accepted
time: 54ms
memory: 11920kb

input:

2
198018
875421126 585870339 471894633 383529988 625397685 944061047 704695631 105113224 459022561 760848605 980735314 847376362 980571959 329939331 644635272 326439858 752879510 837384394 175179068 182094523 397239381 1199016 185143405 279638454 252374970 822030887 860312140 137248166 993229443 164...

output:

4084978
4130372

result:

ok 2 number(s): "4084978 4130372"

Test #3:

score: 0
Accepted
time: 51ms
memory: 11896kb

input:

2
195768
3086 1582 7854 5577 5243 2734 8054 4805 5686 7065 5555 2410 6240 7589 2889 3745 8094 9147 9438 1252 5497 5786 6655 4437 3933 2579 5722 9512 3117 1742 5362 2068 1853 4069 9231 1126 3991 420 2571 5517 3063 7279 8085 6111 5503 5980 50 6003 244 9684 6343 6517 1598 5223 5520 982 3932 1093 1149 7...

output:

3061429
2997931

result:

ok 2 number(s): "3061429 2997931"

Test #4:

score: 0
Accepted
time: 21ms
memory: 12240kb

input:

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

output:

10000000000
9999900003

result:

ok 2 number(s): "10000000000 9999900003"

Test #5:

score: 0
Accepted
time: 50ms
memory: 12024kb

input:

2
200000
200000 1 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 19...

output:

19999700003
19999500006

result:

ok 2 number(s): "19999700003 19999500006"

Test #6:

score: 0
Accepted
time: 40ms
memory: 7800kb

input:

1000
27
373114173 854237870 229115295 303949167 146925508 596279432 662675971 828943670 913666267 642273210 864977718 57938747 337667826 311832042 518751132 911924071 931628414 438636899 404194523 247567493 293431672 743877009 323812958 366701767 976661982 731099528 757329365
267
63595569 149400190 ...

output:

115
2276
570
4717
2719
3150
117
2890
994
3136
3470
6985
4700
327
4127
3761
1493
5117
4734
7698
779
5644
0
5997
2019
823
499
371
6544
1371
7689
5392
850
8358
7737
3302
169
1332
5114
6550
3956
726
6724
3644
5352
431
5469
301
980
6599
3734
6368
7770
6624
1981
4028
4968
183
704
5360
538
1814
7453
6600
5...

result:

ok 1000 numbers

Test #7:

score: 0
Accepted
time: 34ms
memory: 9760kb

input:

1000
424
6 7 9 1 3 9 5 6 4 3 10 8 4 7 9 7 4 5 5 6 4 9 4 1 1 7 4 10 7 4 9 7 1 8 6 1 7 10 6 1 8 2 3 2 5 10 6 7 5 1 2 5 1 6 5 9 9 7 9 4 8 1 4 10 10 4 3 8 3 8 2 4 8 3 10 7 6 7 6 3 8 8 5 9 1 6 2 6 3 7 9 4 9 1 1 3 7 3 2 1 9 4 3 10 6 8 3 5 9 5 7 5 3 8 9 1 3 9 7 8 7 2 10 8 2 2 6 8 8 9 6 2 1 8 8 10 8 9 9 8 1...

output:

1120
617
1562
339
1650
1312
1773
958
100
843
1609
474
1260
1098
1041
1176
1589
932
501
1541
41
384
1859
613
1053
1418
1918
326
1632
1701
1787
1953
969
40
387
489
1442
177
250
149
867
823
890
1809
88
198
858
1926
1948
963
1635
1077
936
558
1722
460
444
188
670
909
1201
943
241
677
511
904
1670
39
245...

result:

ok 1000 numbers

Test #8:

score: 0
Accepted
time: 38ms
memory: 9940kb

input:

40
8008
48 20 89 29 69 45 98 32 81 95 14 76 71 95 78 2 10 70 3 29 17 98 70 46 56 85 26 1 28 29 40 85 11 73 94 56 58 58 29 13 49 39 49 32 23 26 49 57 67 89 84 61 72 66 58 56 90 47 84 45 74 47 100 29 34 87 47 25 83 90 40 31 41 73 4 41 71 35 60 98 48 39 41 7 87 61 81 52 68 13 79 20 100 51 67 4 21 44 36...

output:

56281
60060
57356
68879
61529
70028
66099
65871
68789
72953
58296
56780
66942
69428
56502
59396
60430
72721
55569
68153
53756
69404
61158
55211
57010
71040
71929
54812
73696
58504
68175
70053
68562
68920
67029
57567
63834
69532
54823
64783

result:

ok 40 numbers

Test #9:

score: 0
Accepted
time: 31ms
memory: 12308kb

input:

2
200000
8800 21777 33807 7508 41169 34983 54423 57197 66387 77451 45051 82026 86613 98746 80370 101146 105313 109767 111366 113091 117852 114257 122277 131527 122038 167974 170027 166043 172064 186770 184175 197964 196997 198573 205904 202932 208074 211526 227646 214940 229193 238630 229721 241165 ...

output:

5398667648
5311688815

result:

ok 2 number(s): "5398667648 5311688815"

Test #10:

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

input:

2
200000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

3758431
4322755

result:

ok 2 number(s): "3758431 4322755"

Test #11:

score: 0
Accepted
time: 7ms
memory: 9908kb

input:

2
200000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1...

output:

23515506
29681187

result:

ok 2 number(s): "23515506 29681187"

Test #12:

score: 0
Accepted
time: 37ms
memory: 12216kb

input:

2
200000
999952233 999976412 999940766 999967142 999941003 999930196 999934027 999918088 999918396 999935752 999910715 999896335 999985232 999901405 999881287 999902906 999875401 999855733 999853754 999849824 999872551 999842149 999841957 999841546 999847364 999868855 999831997 999841525 999823216 9...

output:

758309269
2070755309

result:

ok 2 number(s): "758309269 2070755309"

Test #13:

score: 0
Accepted
time: 13ms
memory: 9812kb

input:

2
200000
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...

output:

589267
798840

result:

ok 2 number(s): "589267 798840"

Test #14:

score: 0
Accepted
time: 39ms
memory: 12292kb

input:

2
200000
3 4 3 5 4 1 2 3 1 5 6 3 1 1 1 5 6 6 6 1 6 4 2 5 6 1 5 7 3 1 1 8 2 4 7 8 7 2 1 8 8 9 4 6 7 7 7 5 9 3 9 5 7 8 5 7 3 5 4 7 1 3 8 8 1 4 3 3 8 2 9 11 3 9 8 9 9 11 11 8 10 9 12 9 2 10 1 10 7 10 9 2 9 10 13 9 4 10 13 12 13 8 7 13 9 14 11 14 4 14 8 14 13 12 10 9 15 10 11 5 2 9 14 12 15 14 16 3 16 1...

output:

1140065663
247172098

result:

ok 2 number(s): "1140065663 247172098"

Extra Test:

score: 0
Extra Test Passed