QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84317#5338. Palindromeszlt100 ✓664ms3868kbC++142.6kb2023-03-06 10:34:452023-03-06 10:34:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 10:34:48]
  • 评测
  • 测评结果:100
  • 用时:664ms
  • 内存:3868kb
  • [2023-03-06 10:34:45]
  • 提交

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'