QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #122555 | #6539. Treasure Box | Scarlett_boy | AC ✓ | 758ms | 100744kb | C++17 | 7.4kb | 2023-07-10 19:07:18 | 2023-07-10 19:07:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
#define int long long
int n, c;
char s[N];
int Cost[N];
ll Val[N];
struct Segment_Tree {
vector<int> tag, Min;
int Mi = 1, Ma = 1e9;
Segment_Tree(int M) : tag((M + 1) * 4, 0), Min((M + 1) * 4, 0) { Ma = M; }
inline void pushup(int &p) {
Min[p] = min(Min[p << 1], Min[p << 1 | 1]);
}
inline void pushdown(int &p, int &l, int &r, int &mid) {
if (tag[p]) {
int &W = tag[p];
Min[p << 1] += W, Min[p << 1 | 1] += W;
tag[p << 1] += W, tag[p << 1 | 1] += W;
W = 0;
}
}
inline void add(int p, int l, int r, int x, int y, int w) {
if (x <= l && r <= y) {
Min[p] += w;
tag[p] += w;
return;
}
int mid = l + r >> 1;
pushdown(p, l, r, mid);
if (x <= mid) add(p << 1, l, mid, x, y, w);
if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, w);
pushup(p);
}
inline void add(int x, int y, int w) { add(1, Mi, Ma, x, y, w); }
inline int query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) return Min[p];
int mid = l + r >> 1, Ans = LLONG_MAX;
pushdown(p, l, r, mid);
if (x <= mid) Ans = min(Ans, query(p << 1, l, mid, x, y));
if (y > mid) Ans = min(Ans, query(p << 1 | 1, mid + 1, r, x, y));
return Ans;
}
inline int query(int l, int r) { return query(1, Mi, Ma, l, r); }
};
ll Ans[N];
int ZZ;
void SOLVE() {
ll Sum = 0;
for (int i = 1; i <= ZZ; i++) {
if (s[i] != s[n + 1 - i]) Sum += Cost[i];
}
Val[ZZ] = Sum;
for (int i = ZZ + 1; i <= n; i++) {
if (s[i] == s[n - i + 1]) Val[i] = Val[i - 1];
else {
Val[i] = Val[i - 1] + min(Cost[i], Cost[n + 1 - i]) - Cost[n + 1 - i];
}
}
Segment_Tree T(n);
for (int i = ZZ; i <= n; i++) {
T.add(i, i, Val[i] + (i - 1) * c);
}
Ans[1] = min(Ans[1], T.query(ZZ, n));
int Left = ZZ, L = ZZ;
int half = n / 2;
for (int i = 2; i <= n; i++) {
if (i > half) {
if (n & 1) {
if (i == half + 1) {
T.add(Left, i - 1, c);
if (i <= n - 2) T.add(i, n - 2, -c);
T.add(n, n, c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
} else {
if (i == half + 1) {
T.add(Left, i - 1, c);
if (i < n) T.add(i, n - 1, -c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
}
} else if (i > Left) {
T.add(Left, i - 1, c);
int R = 2 * i - 1;
T.add(R, n, c);
if (L % 2 == 0) {
if (L > Left) T.add(i, L - 1, -c);
} else {
T.add(i, L, -c);
}
L = R;
} else {// ZZ < i < Half
int R = 2 * i - 1;
if (R <= Left) {
T.add(Left, n, c);
} else {
T.add(R, n, c);
if (L % 2 == 0) {
if (L > Left) T.add(Left, L - 1, -c);
} else {
T.add(Left, L, -c);
}
L = R;
}
}
Ans[i] = min(Ans[i], T.query(ZZ, n));
}
}
void SOLVE2() {
reverse(s + 1, s + 1 + n);
reverse(Cost + 1, Cost + 1 + n);
ll Sum = 0;
for (int i = 1; i <= ZZ; i++) {
if (s[i] != s[n + 1 - i]) Sum += Cost[i];
}
Val[ZZ] = Sum;
for (int i = ZZ + 1; i <= n; i++) {
if (s[i] == s[n - i + 1]) Val[i] = Val[i - 1];
else {
Val[i] = Val[i - 1] + min(Cost[i], Cost[n + 1 - i]) - Cost[n + 1 - i];
}
}
// for (int i = n / 2; i <= n; i++) {
// cout << " " << Val[i] << " ";
// }
// cout << "\n";
Segment_Tree T(n);
for (int i = ZZ; i <= n; i++) {
// cout << " " << Val[i] + (i - 1) * c << " \n"[i == n];
T.add(i, i, Val[i] + (i - 1) * c);
}
Ans[n] = min(Ans[n], T.query(ZZ, n));
// for (int j = n / 2; j <= n; j++) {
// cout << T.query(j, j) << " \n"[j == n];
// }
int Left = ZZ, L = ZZ;
int half = n / 2;
for (int i = 2; i <= n; i++) {
if (i > half) {
if (n & 1) {
if (i == half + 1) {
T.add(Left, i - 1, c);
if (i <= n - 2) T.add(i, n - 2, -c);
T.add(n, n, c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
} else {
if (i == half + 1) {
T.add(Left, i - 1, c);
if (i < n) T.add(i, n - 1, -c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
}
} else if (i > Left) {
T.add(Left, i - 1, c);
int R = 2 * i - 1;
T.add(R, n, c);
if (L % 2 == 0) {
if (L > Left) T.add(i, L - 1, -c);
} else {
T.add(i, L, -c);
}
L = R;
} else {// ZZ < i < Half
int R = 2 * i - 1;
if (R <= Left) {
T.add(Left, n, c);
} else {
T.add(R, n, c);
if (L % 2 == 0) {
if (L > Left) T.add(Left, L - 1, -c);
} else {
T.add(Left, L, -c);
}
L = R;
}
}
Ans[n + 1 - i] = min(Ans[n + 1 - i], T.query(ZZ, n));
}
}
char ss[N];
int Z;
int C[N];
int nn;
void init() {
cin >> nn >> c;
cin >> (ss + 1);
for (int i = 1; i <= nn; i++) {
cin >> C[i];
}
int pos = 1;
for (int i = 1; i <= nn; i++) {
if (ss[i] != ss[nn - i + 1]) {
pos = i;
break;
}
}
Z = pos;
n = nn - (pos - 1) * 2;
for (int i = 1; i <= n; i++) {
s[i] = ss[pos + i - 1];
Cost[i] = C[pos + i - 1];
}
for (int i = n / 2; i >= 1; i--) {
if (s[n - i + 1] != s[i]) {
ZZ = i;
break;
}
}
}
void solve() {
init();
vector<int> vec;
for (int i = 1; i <= n; i++) {
if (s[i] != s[n + 1 - i]) {
vec.push_back(i);
}
}
if (vec.empty()) {
for (int i = 1; i <= n; i++) cout << 0 << " \n"[i == n];
return;
}
for (int i = 1; i <= n; i++) Ans[i] = LLONG_MAX;
SOLVE();
SOLVE2();
for (int i = 1; i < Z; i++) {
cout << Ans[1] + (Z - i) * c << " ";
}
for (int i = 1; i <= n; i++) cout << Ans[i] << " ";
for (int i = 1; i < Z; i++) {
cout << Ans[n] + (i) * c << " ";
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
cin >> _;
for (int o = 1; o <= _; o++) {
// cout << "Case #<<" << o << ": ";
solve();
}
return 0;
}
/*
1
10 4
AABABBABAB
10 3 4 10 7 1 8 10 7 6
*/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13716kb
input:
2 5 1 ABCDE 7 1 4 5 1 5 1 ABCDA 7 1 4 5 1
output:
6 5 6 6 5 2 1 2 3 4
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 11684kb
input:
1 10 4 AABABBABAB 10 3 4 10 7 1 8 10 7 6
output:
10 14 18 22 26 22 18 14 10 6
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 17ms
memory: 9648kb
input:
10000 10 4 ABBBAABABB 6 10 3 9 1 8 5 4 4 10 10 4 BABBAAABAB 3 7 5 9 2 3 9 8 4 1 10 4 ABBBAAABAA 3 2 4 8 2 9 1 9 6 3 10 4 BBAABBAABB 8 8 10 7 1 1 4 9 6 4 10 4 BAABBBBBAB 5 7 3 5 4 2 1 8 2 8 10 4 ABAAAABABA 10 8 2 7 5 3 7 8 10 5 10 4 BBABABAABA 10 6 10 2 2 6 4 4 3 9 10 4 BBBAAAABBB 7 2 2 8 9 10 10 6 7...
output:
17 21 17 21 25 29 26 22 26 22 21 17 13 9 13 13 9 13 17 21 22 18 22 18 22 19 15 19 15 19 0 0 0 0 0 0 0 0 0 0 11 7 3 7 11 15 12 8 12 16 19 15 11 7 11 11 7 11 15 19 30 34 38 34 30 34 38 42 39 35 0 0 0 0 0 0 0 0 0 0 11 7 3 7 11 13 9 5 9 13 8 4 8 12 16 14 10 6 2 6 18 14 10 6 10 14 10 14 18 22 27...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 153ms
memory: 13712kb
input:
100000 10 4 BABBBABBAB 8 2 3 10 2 1 10 1 6 4 10 4 BBBAAAABBB 6 4 8 2 6 5 3 7 8 1 10 4 ABAAABAAAB 9 8 8 1 5 4 7 8 2 1 10 4 ABABBBBAAA 8 6 6 3 10 4 5 4 7 3 10 4 AABAABABBA 3 9 9 1 5 6 4 8 2 6 10 4 ABBBAABBBA 7 1 10 2 1 5 1 8 3 7 10 4 BAAABBBAAB 7 10 5 5 1 5 3 5 1 7 10 4 BABAAAAAAB 10 8 7 6 7 10 10 4 8...
output:
18 14 10 6 2 1 5 9 13 17 0 0 0 0 0 0 0 0 0 0 38 39 35 31 27 23 27 31 27 23 10 6 10 14 18 19 15 11 7 11 30 26 30 27 23 20 24 24 20 24 0 0 0 0 0 0 0 0 0 0 17 13 9 5 9 7 3 7 11 15 15 11 7 11 15 12 8 4 8 12 4 8 12 16 20 17 13 9 5 1 15 11 7 11 15 11 7 3 7 11 31 27 31 31 27 24 28 28 24 28 17 21 2...
result:
ok 1000000 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 9728kb
input:
1 1000 4 BABABABBBBABAAAAAABAABBBBBBBBABBBAAAAAABBBBAAABBABABBBBABBBBBBABABBBBAABAAABBBBBBAABABBBAAABABAAAABBBBAAABAABBBABBBAAABBABABABBABAAABAAABBABABABBABAABAABAAABBBBAAABBABBBBABAAABBABBBAAABBABBAABABBABAAAAAABBABAAAABBBBBAABAABBABABAABBAAABBBAAABABAAAABAABBAAABBBAABBABABABBAAAAABBBAAAAAAAABAABBB...
output:
3441 3437 3441 3445 3449 3453 3457 3461 3465 3469 3473 3477 3481 3485 3489 3493 3497 3501 3505 3509 3513 3517 3521 3525 3529 3533 3537 3541 3545 3549 3553 3557 3561 3565 3569 3573 3577 3581 3585 3589 3593 3597 3601 3605 3609 3613 3617 3621 3625 3629 3633 3637 3641 3645 3649 3653 3657 3661 3665 3669 ...
result:
ok 1000 numbers
Test #6:
score: 0
Accepted
time: 387ms
memory: 9724kb
input:
1000 1000 4 ABBABBBABBABBAABBABABAAABABAAABAAABAAABABABABABBBAABABBAABAABBBAABBBABBAABAAABBABAAABAAAABAAAAABBBBABBAAABBBABBABABBBABABBABAAABBBBAABBAAABAABBAABBAAAAABAAAABBABBABBAAABBAABBBBABBBAABAAAABAAAAABAAAABABABBBAABBBABAAABBBAAABAAAAABBABAABBABBBAABAABBBBBBAABABBBAAAABBABBAAABBBABBBBABAABAAAABA...
output:
3316 3312 3316 3320 3324 3328 3332 3336 3340 3344 3348 3352 3356 3360 3364 3368 3372 3376 3380 3384 3388 3392 3396 3400 3404 3408 3412 3416 3420 3424 3428 3432 3436 3440 3444 3448 3452 3456 3460 3464 3468 3472 3476 3480 3484 3488 3492 3496 3500 3504 3508 3512 3516 3520 3524 3528 3532 3536 3540 3544 ...
result:
ok 1000000 numbers
Test #7:
score: 0
Accepted
time: 401ms
memory: 13748kb
input:
1000 1000 4 BAABAABAABABABBBABBBAAAABAAAABBAAAABABABAABBBABBBAABBBBABAAABBAABBAAAABAABAAABAAAABAAABBABAAAAABABBBAAABAAAABAABBAAAABBBBAAABBBBBABAABBBBAAAAAABABBBBAABBABBAABABBABAAAAAABAABBABBBAAAAAABAABBABBBBABBBBAAAAAABABBABBABAABABBBBBBABBAABBBAAAAAAAABAAAAAAAAAAABBBBAAABBAABBAAABBBBBABAAAAABBABAAB...
output:
2691 2695 2699 2703 2707 2711 2715 2719 2723 2727 2731 2735 2739 2743 2747 2751 2755 2759 2763 2767 2771 2775 2779 2783 2787 2791 2795 2799 2803 2807 2811 2815 2819 2823 2827 2831 2835 2839 2843 2847 2851 2855 2859 2863 2867 2871 2875 2879 2883 2887 2891 2895 2899 2903 2907 2911 2915 2919 2923 2927 ...
result:
ok 1000000 numbers
Test #8:
score: 0
Accepted
time: 596ms
memory: 38808kb
input:
3 300000 4 BBBBAABABAABBBBBBBBBAAAABAABABBBBABBAABABBBAABABAAABAAABAAAAABAABAAABABBABAABBBBBAABBABAAABAABAABBBAAAAAAABBABABBBABABBBBBBBABBAAAAAABBBABBBBAABAAABBBBABAABAABBAABBAAAABBBABBBAAABAAABAAABABBABBABABBBABBBABABAABBABBBBABAAAABABBAABABAAABABBBBBAABBBABAAAAAAABAAAAAAAABBAAABABBBBBBABAABBBBAABA...
output:
1009294 1009290 1009294 1009298 1009302 1009306 1009310 1009314 1009318 1009322 1009326 1009330 1009334 1009338 1009342 1009346 1009350 1009354 1009358 1009362 1009366 1009370 1009374 1009378 1009382 1009386 1009390 1009394 1009398 1009402 1009406 1009410 1009414 1009418 1009422 1009426 1009430 1009...
result:
ok 900000 numbers
Test #9:
score: 0
Accepted
time: 617ms
memory: 44636kb
input:
3 300000 4 AAAABBBBABAABBBBBABBBABAAABAABBBAAAAABBBAABAABABBABBAAAABBABABBAAABBBBAABBBBBBBBAAABBABBBBBABBABABBBABABBBBBBBABBABBAAABBBBBBBABABABBBABABBAABBBBABABAAAABBABBAAAABBBBAABABABAAAABAAABABBBBAABBBABBBBBBABBBAABBAABBAABBBAABABABBBBABBBAAAABBBAABABBBBABAAAABAAAABABBBAABBABABBBABAABABABBABABAAAA...
output:
640825 640821 640817 640821 640825 640829 640833 640837 640841 640845 640849 640853 640857 640861 640865 640869 640873 640877 640881 640885 640889 640893 640897 640901 640905 640909 640913 640917 640921 640925 640929 640933 640937 640941 640945 640949 640953 640957 640961 640965 640969 640973 640977...
result:
ok 900000 numbers
Test #10:
score: 0
Accepted
time: 637ms
memory: 47748kb
input:
3 300000 123123123 BAAABBAABAAAAAAABBBAAABABBBBBBABBAAABAAAABBBBAAAAAABABBBBBBBAAAAAABABABAABBAAABBABBAAABAAAABBBBAAAAABABBBABAABABAAABABBBAAAABBABABBABABBBBBAAABBAABABABBABBBABBBAAAAABAAABAABBBAAAAAAABBBBBABBBAABABBAABAAAAAAAABAAABAABBAAAAABABABAABBABABBAAABAAAAAABBABBBBABAABABAAAAAAABBABABBAAAAAAA...
output:
55885802355459 55885925478582 55886048601705 55886171724828 55886294847951 55886417971074 55886541094197 55886664217320 55886787340443 55886910463566 55887033586689 55887156709812 55887279832935 55887402956058 55887526079181 55887649202304 55887772325427 55887895448550 55888018571673 55888141694796 ...
result:
ok 900000 numbers
Test #11:
score: 0
Accepted
time: 626ms
memory: 42212kb
input:
3 300000 12312 BABBBAAAAAAABABAAABAAABABABBAAAABBBBBAABBABABBBABBAABABABABBABBAAABABABBAABAAABABAABBAAABAAAAAAAABAABBAABBBBBABABBAABBABAAABAAABBBBBABBABBAABBABBBBBABAAABBAAABBBBABBAABAAAAABBABBAABABABABBBABAABBABBBABBBBAAABABAABAAAAABBAAABABAAABBBBBABAABABABAABABABBBBBABAAAAAABBBABBBBBAAABABBABABBBB...
output:
12476794200881 12476794213193 12476794225505 12476794237817 12476794250129 12476794262441 12476794274753 12476794287065 12476794299377 12476794311689 12476794324001 12476794336313 12476794348625 12476794360937 12476794373249 12476794385561 12476794397873 12476794410185 12476794422497 12476794434809 ...
result:
ok 900000 numbers
Test #12:
score: 0
Accepted
time: 613ms
memory: 42460kb
input:
3 300000 1 BAABAAABABBAAAABAAABABBBAABBABABAABABAABBBAABABAAAABBAABAABBBAABBABABBBABBBAABAAABAABBAAAAAAABAABBABAAABAABBAABABBAABAAAABABBABAAAABBBBBAAAAAABABAAABBABBABABBAAABBBABABBBBBBBBABBBABBBBBBABBBAAAABAABAABBBAABBAABAAABBAAAABBBABBBBAABBABABAABBBAABBBBAABAAAABBAABBBABBBBAAABBAABAAAABBABABBABBBB...
output:
2542442846144 2542442846143 2542442846142 2542442846141 2542442846140 2542442846139 2542442846138 2542442846137 2542442846136 2542442846135 2542442846134 2542442846133 2542442846132 2542442846131 2542442846130 2542442846129 2542442846128 2542442846127 2542442846126 2542442846125 2542442846124 254244...
result:
ok 900000 numbers
Test #13:
score: 0
Accepted
time: 596ms
memory: 41232kb
input:
3 300000 1 BABAABBBAABBBABBABABAABBAAAAABBABBABBBABABABABBBBABAABABBBBAABABBBAAAABAAAABBAAAABBBBAABAAABBABAAAABBAAAAABABBAABABAABBBABBAABAAABBAABAAABBAABBBAAABBAABBAAABBABAABBAAABAABBBBAAABBBAAABBAABBABBBBBAAAABBABABAAAAABBAABBBAABBAABBABAABABBBBABBBBAABBBBAAAAAAAAAAABBBABBBBBBBABBAABBAABAAAAABBABAA...
output:
24764949682507 24764949682508 24764949682509 24764949682510 24764949682511 24764949682512 24764949682513 24764949682514 24764949682515 24764949682516 24764949682517 24764949682518 24764949682519 24764949682520 24764949682521 24764949682522 24764949682523 24764949682524 24764949682525 24764949682526 ...
result:
ok 900000 numbers
Test #14:
score: 0
Accepted
time: 758ms
memory: 100744kb
input:
1 1000000 1234123 BBABABBBAABBAAAAAABBBBBABABBBBBAAABAABBAAABBABBAAAABBABAAABABAAAABABAAABBBBBABABAABBBBBAABBABABAAABABBABBBBAABBAABABABBBAABAABAAAAAABBBABABBBAABAABABBBAABAABABAAABBAABAAABAABABABBAAAABBBAAAABBBABBBAABABAABBBBBABBBBBAABBBBBBABABBBBBBBABBBABBABBBAAAABBAAABBBBBBAABAAABBBABABBBBAAABBAB...
output:
84824683190883 84824684425006 84824685659129 84824686893252 84824688127375 84824689361498 84824690595621 84824691829744 84824693063867 84824694297990 84824695532113 84824696766236 84824698000359 84824699234482 84824700468605 84824701702728 84824702936851 84824704170974 84824705405097 84824706639220 ...
result:
ok 1000000 numbers