QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84973#5338. PalindromesBird100 ✓260ms3812kbC++14898b2023-03-06 21:26:192023-03-06 21:26:51

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 21:26:51]
  • 评测
  • 测评结果:100
  • 用时:260ms
  • 内存:3812kb
  • [2023-03-06 21:26:19]
  • 提交

answer

#include<bits/stdc++.h>
#define N 7500
using namespace std;
int n,p[N+5],cnt[N*2+5],ps1,ss1,x;
long long ps2,ss2;
char s[N+5];
long long ans;
inline void add() {ss1-=cnt[x],ss2-=ss1;ps2+=ps1,ps1+=cnt[++x];}
inline void sub() {ps1-=cnt[x],ps2-=ps1;ss2+=ss1,ss1+=cnt[--x];}
int main()
{
	scanf("%s",s+1);
	for(int i=1;s[i];++i) if(s[i]=='G') p[++n]=i;
	p[0]=0,p[n+1]=strlen(s+1)+1;
	for(int i=1;i<=n;++i) for(int j=i;j<=min(i+1,n);++j)
	{
		memset(cnt,0,sizeof cnt),x=p[i]+p[j],ps1=ss1=0,ps2=ss2=0;
		for(int k=0;i-k && j+k<=n;++k)
		{
			int l1=p[i-k],l2=p[i-k-1],r1=p[j+k],r2=p[j+k+1];
			if(l1!=r1) ++cnt[l1+r1],++ps1,++ss1;
			for(int l=l1;l>l2;--l,sub())
			{
				for(int r=r1;r<r2;++r,add())
					if(i==j) ans+=(r-l)&1?-1:ps2+ss2+abs(p[i]-x/2);
					else ans+=ps2+ss2;
				if(l!=l2+1) for(int r=r2;r>r1;--r,sub());
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 6.25
Accepted
time: 2ms
memory: 3588kb

input:

GHHGGHHGH

output:

12

result:

ok single line: '12'

Test #2:

score: 6.25
Accepted
time: 2ms
memory: 3796kb

input:

HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG

output:

98047

result:

ok single line: '98047'

Test #3:

score: 6.25
Accepted
time: 0ms
memory: 3584kb

input:

GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG

output:

1377709

result:

ok single line: '1377709'

Test #4:

score: 6.25
Accepted
time: 1ms
memory: 3588kb

input:

HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...

output:

18589853

result:

ok single line: '18589853'

Test #5:

score: 6.25
Accepted
time: 8ms
memory: 3616kb

input:

GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...

output:

239620295

result:

ok single line: '239620295'

Test #6:

score: 6.25
Accepted
time: 20ms
memory: 3560kb

input:

GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...

output:

3749745269

result:

ok single line: '3749745269'

Test #7:

score: 6.25
Accepted
time: 130ms
memory: 3804kb

input:

HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...

output:

81813329996

result:

ok single line: '81813329996'

Test #8:

score: 6.25
Accepted
time: 108ms
memory: 3536kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...

output:

1993575766369

result:

ok single line: '1993575766369'

Test #9:

score: 6.25
Accepted
time: 110ms
memory: 3780kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...

output:

1936319118814

result:

ok single line: '1936319118814'

Test #10:

score: 6.25
Accepted
time: 114ms
memory: 3572kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...

output:

1906624646754

result:

ok single line: '1906624646754'

Test #11:

score: 6.25
Accepted
time: 105ms
memory: 3780kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...

output:

2056784748165

result:

ok single line: '2056784748165'

Test #12:

score: 6.25
Accepted
time: 260ms
memory: 3812kb

input:

HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...

output:

516066376178

result:

ok single line: '516066376178'

Test #13:

score: 6.25
Accepted
time: 224ms
memory: 3576kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9878475549129

result:

ok single line: '9878475549129'

Test #14:

score: 6.25
Accepted
time: 229ms
memory: 3748kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9918848392027

result:

ok single line: '9918848392027'

Test #15:

score: 6.25
Accepted
time: 232ms
memory: 3604kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...

output:

9882416063183

result:

ok single line: '9882416063183'

Test #16:

score: 6.25
Accepted
time: 231ms
memory: 3784kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...

output:

9847097832382

result:

ok single line: '9847097832382'