QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#567357 | #9313. Make Max | Kelvin_L | AC ✓ | 54ms | 12308kb | C++14 | 1.0kb | 2024-09-16 11:21:10 | 2024-09-18 15:57:37 |
Judging History
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