QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69358#5338. Palindromeschenshi100 ✓388ms1760kbC++1.1kb2022-12-26 20:28:122022-12-26 20:28:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-26 20:28:15]
  • 评测
  • 测评结果:100
  • 用时:388ms
  • 内存:1760kb
  • [2022-12-26 20:28:12]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int o=1e5;
int n,st[o],tp,b1[o],b2[o],s1,s2;long long ans;char s[o];
inline void clear(){
	s1=s2=0;
	for(int i=1;i<=n*2;++i) b1[i]=b2[i]=0;
}
inline int lowbit(int x){return x&-x;}
inline void modify(int pos,int v1,int v2){s1+=v1;s2+=v2;for(;pos<=n*2;pos+=lowbit(pos)) b1[pos]+=v1,b2[pos]+=v2;}
inline int query(int pos){
	int res1=0,res2=0,t=pos;
	for(;pos;pos-=lowbit(pos)) res1+=b1[pos],res2+=b2[pos];
	return res1*t-res2+s2-res2-(s1-res1)*t;
}
int main(){
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;++i) if(s[i]=='G') st[++tp]=i;
	st[tp+1]=n+1;
	for(int i=1;i<=tp;++i){
		clear();
		for(int L=i,R=i;L&&R<=tp;--L,++R){
			if(L<R) modify(st[L]+st[R],1,st[L]+st[R]);
			for(int l=st[L];l>st[L-1];--l) for(int r=st[R];r<st[R+1];++r)
				if((r-l+1)&1) ans+=query(l+r)+abs((l+r)/2-st[i]);else --ans;
		}
	}
	for(int i=1;i<tp;++i){
		clear();
		for(int L=i,R=i+1;L&&R<=tp;--L,++R){
			modify(st[L]+st[R],1,st[L]+st[R]);
			for(int l=st[L];l>st[L-1];--l) for(int r=st[R];r<st[R+1];++r) ans+=query(l+r);
		}
	}
	printf("%lld",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

GHHGGHHGH

output:

12

result:

ok single line: '12'

Test #2:

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

input:

HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG

output:

98047

result:

ok single line: '98047'

Test #3:

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

input:

GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG

output:

1377709

result:

ok single line: '1377709'

Test #4:

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

input:

HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...

output:

18589853

result:

ok single line: '18589853'

Test #5:

score: 6.25
Accepted
time: 7ms
memory: 1680kb

input:

GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...

output:

239620295

result:

ok single line: '239620295'

Test #6:

score: 6.25
Accepted
time: 26ms
memory: 1616kb

input:

GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...

output:

3749745269

result:

ok single line: '3749745269'

Test #7:

score: 6.25
Accepted
time: 171ms
memory: 1672kb

input:

HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...

output:

81813329996

result:

ok single line: '81813329996'

Test #8:

score: 6.25
Accepted
time: 151ms
memory: 1556kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...

output:

1993575766369

result:

ok single line: '1993575766369'

Test #9:

score: 6.25
Accepted
time: 155ms
memory: 1580kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...

output:

1936319118814

result:

ok single line: '1936319118814'

Test #10:

score: 6.25
Accepted
time: 152ms
memory: 1672kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...

output:

1906624646754

result:

ok single line: '1906624646754'

Test #11:

score: 6.25
Accepted
time: 149ms
memory: 1756kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...

output:

2056784748165

result:

ok single line: '2056784748165'

Test #12:

score: 6.25
Accepted
time: 388ms
memory: 1676kb

input:

HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...

output:

516066376178

result:

ok single line: '516066376178'

Test #13:

score: 6.25
Accepted
time: 339ms
memory: 1716kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9878475549129

result:

ok single line: '9878475549129'

Test #14:

score: 6.25
Accepted
time: 347ms
memory: 1760kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9918848392027

result:

ok single line: '9918848392027'

Test #15:

score: 6.25
Accepted
time: 350ms
memory: 1712kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...

output:

9882416063183

result:

ok single line: '9882416063183'

Test #16:

score: 6.25
Accepted
time: 355ms
memory: 1748kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...

output:

9847097832382

result:

ok single line: '9847097832382'