QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84317 | #5338. Palindromes | zlt | 100 ✓ | 664ms | 3868kb | C++14 | 2.6kb | 2023-03-06 10:34:45 | 2023-03-06 10:34:48 |
Judging History
answer
// Problem: P8908 [USACO22DEC] Palindromes P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8908
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 7510;
int n, a[maxn], b[maxn];
char _s[maxn];
struct BIT {
int c[maxn << 1];
inline void clear() {
mems(c, 0);
}
inline void update(int x, int d) {
for (int i = x; i <= n * 2; i += (i & (-i))) {
c[i] += d;
}
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
} t1, t2;
void solve() {
scanf("%s", _s + 1);
n = strlen(_s + 1);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
a[i] = (_s[i] == 'G');
cnt += a[i];
}
if (cnt > n / 2) {
for (int i = 1; i <= n; ++i) {
a[i] ^= 1;
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
int tot = 0;
for (int j = i; j <= n; ++j) {
if (a[j]) {
b[++tot] = j;
}
if ((tot & 1) && (j - i + 1) % 2 == 0) {
--ans;
} else if (tot & 1) {
ans += 1LL * abs((i + j) / 2 - b[(tot + 1) / 2]);
}
}
}
int tot = 0;
for (int i = 1; i <= n; ++i) {
if (a[i]) {
b[++tot] = i;
}
}
b[tot + 1] = n + 1;
for (int i = 1; i <= tot; ++i) {
t1.clear();
t2.clear();
int s = 0, c = 0;
for (int j = 1; i - j >= 1 && i + j <= tot; ++j) {
int t = b[i - j] + b[i + j];
t1.update(t, 1);
t2.update(t, t);
s += t;
++c;
for (int l = b[i - j - 1] + 1; l <= b[i - j]; ++l) {
for (int r = b[i + j]; r < b[i + j + 1]; ++r) {
if ((r - l + 1) % 2 == 0) {
continue;
}
ll s1 = t1.query(l + r), s2 = t2.query(l + r);
ans += s1 * (l + r) - s2 + (s - s2) - (c - s1) * (l + r);
}
}
}
}
for (int i = 1; i < tot; ++i) {
t1.clear();
t2.clear();
int s = 0, c = 0;
for (int j = 0; i - j >= 1 && i + j + 1 <= tot; ++j) {
int t = b[i - j] + b[i + j + 1];
t1.update(t, 1);
t2.update(t, t);
s += t;
++c;
for (int l = b[i - j - 1] + 1; l <= b[i - j]; ++l) {
for (int r = b[i + j + 1]; r < b[i + j + 2]; ++r) {
ll s1 = t1.query(l + r), s2 = t2.query(l + r);
ans += s1 * (l + r) - s2 + (s - s2) - (c - s1) * (l + r);
}
}
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 6.25
Accepted
time: 2ms
memory: 3656kb
input:
GHHGGHHGH
output:
12
result:
ok single line: '12'
Test #2:
score: 6.25
Accepted
time: 2ms
memory: 3592kb
input:
HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG
output:
98047
result:
ok single line: '98047'
Test #3:
score: 6.25
Accepted
time: 3ms
memory: 3616kb
input:
GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG
output:
1377709
result:
ok single line: '1377709'
Test #4:
score: 6.25
Accepted
time: 6ms
memory: 3656kb
input:
HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...
output:
18589853
result:
ok single line: '18589853'
Test #5:
score: 6.25
Accepted
time: 14ms
memory: 3624kb
input:
GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...
output:
239620295
result:
ok single line: '239620295'
Test #6:
score: 6.25
Accepted
time: 44ms
memory: 3604kb
input:
GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...
output:
3749745269
result:
ok single line: '3749745269'
Test #7:
score: 6.25
Accepted
time: 284ms
memory: 3704kb
input:
HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...
output:
81813329996
result:
ok single line: '81813329996'
Test #8:
score: 6.25
Accepted
time: 237ms
memory: 3720kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...
output:
1993575766369
result:
ok single line: '1993575766369'
Test #9:
score: 6.25
Accepted
time: 242ms
memory: 3828kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...
output:
1936319118814
result:
ok single line: '1936319118814'
Test #10:
score: 6.25
Accepted
time: 235ms
memory: 3668kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...
output:
1906624646754
result:
ok single line: '1906624646754'
Test #11:
score: 6.25
Accepted
time: 253ms
memory: 3624kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...
output:
2056784748165
result:
ok single line: '2056784748165'
Test #12:
score: 6.25
Accepted
time: 664ms
memory: 3636kb
input:
HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...
output:
516066376178
result:
ok single line: '516066376178'
Test #13:
score: 6.25
Accepted
time: 606ms
memory: 3676kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...
output:
9878475549129
result:
ok single line: '9878475549129'
Test #14:
score: 6.25
Accepted
time: 522ms
memory: 3868kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...
output:
9918848392027
result:
ok single line: '9918848392027'
Test #15:
score: 6.25
Accepted
time: 512ms
memory: 3636kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...
output:
9882416063183
result:
ok single line: '9882416063183'
Test #16:
score: 6.25
Accepted
time: 552ms
memory: 3720kb
input:
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...
output:
9847097832382
result:
ok single line: '9847097832382'