QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #122525 | #6539. Treasure Box | Scarlett_boy | WA | 2ms | 11616kb | C++17 | 7.2kb | 2023-07-10 17:46:37 | 2023-07-10 17:46:40 |
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];
void SOLVE() {
ll Sum = 0;
for (int i = 1; i <= n / 2; i++) {
if (s[i] != s[n + 1 - i]) Sum += Cost[i];
}
Val[n / 2] = Sum;
for (int i = n / 2 + 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 = n / 2; i <= n; i++) {
// cout << " " << Val[i] + (i - 1) * c << " \n"[i == n];
T.add(i, i, Val[i] + (i - 1) * c);
}
Ans[1] = min(Ans[1], T.query(n / 2, n));
// for (int j = n / 2; j <= n; j++) {
// cout << T.query(j, j) << " \n"[j == n];
// }
int Left = n / 2, L = n / 2;
for (int i = 2; i <= n; i++) {
// cout << i << ": ";
if (i > Left) {
if (n & 1) {
if (i == Left + 1) {
T.add(Left, Left, 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 == Left + 1) {
T.add(Left, Left, c);
if (i < n)T.add(i, n - 1, -c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
}
} else {
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;
}
}
// for (int j = n / 2; j <= n; j++) {
// cout << T.query(j, j) << " \n"[j == n];
// }
Ans[i] = min(Ans[i], T.query(Left, n));
}
}
void SOLVE2() {
reverse(s + 1, s + 1 + n);
reverse(Cost + 1, Cost + 1 + n);
ll Sum = 0;
for (int i = 1; i <= n / 2; i++) {
if (s[i] != s[n + 1 - i]) Sum += Cost[i];
}
Val[n / 2] = Sum;
for (int i = n / 2 + 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 = n / 2; 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(n / 2, n));
// for (int j = n / 2; j <= n; j++) {
// cout << T.query(j, j) << " \n"[j == n];
// }
int Left = n / 2, L = n / 2;
for (int i = 2; i <= n; i++) {
// cout << i << ": ";
if (i > Left) {
if (n & 1) {
if (i == Left + 1) {
T.add(Left, Left, 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 == Left + 1) {
T.add(Left, Left, c);
if (i < n)T.add(i, n - 1, -c);
} else {
T.add(Left, i - 1, c);
T.add(i, n, -c);
}
}
} else {
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;
}
}
// for (int j = n / 2; j <= n; j++) {
// cout << T.query(j, j) << " \n"[j == n];
// }
Ans[n + 1 - i] = min(Ans[n + 1 - i], T.query(Left, 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];
}
}
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
5 1
ABCDE
7 1 4 5 1
1
5 1
ABCDA
7 1 4 5 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9512kb
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: -100
Wrong Answer
time: 2ms
memory: 11616kb
input:
1 10 4 AABABBABAB 10 3 4 10 7 1 8 10 7 6
output:
26 30 34 30 26 22 26 30 26 22
result:
wrong answer 1st numbers differ - expected: '10', found: '26'