QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84970#5338. Palindromesfzj2007100 ✓770ms3812kbC++142.9kb2023-03-06 21:25:092023-03-06 21:25:38

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:25:38]
  • 评测
  • 测评结果:100
  • 用时:770ms
  • 内存:3812kb
  • [2023-03-06 21:25:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	template<typename T>inline bool read(T &x){
		x=0;
		char ch=getchar();
		bool flag=0,ret=0;
		while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
		x=flag?-x:x;
        return ret;
	}
	template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
	    return read(a)&&read(args...);
	}
	template<typename T>void prt(T x){
		if(x>9) prt(x/10);
		putchar(x%10+'0');
	}
	template<typename T>inline void put(T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
	}
	template<typename T>inline void put(char ch,T x){
		if(x<0) putchar('-'),x=-x;
		prt(x);
		putchar(ch);
	}
	template<typename T,typename ...Args>inline void put(T a,Args ...args){
	    put(a);
		put(args...);
	}
	template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
	    put(ch,a);
		put(ch,args...);
	}
	inline void put(string s){
		for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
	}
	inline void put(const char* s){
		for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
	}
}
using namespace IO;
#define N 7505
#define M 15000
#define ll long long
char s[N];
int n,p[N],pre[N],m;
ll ans;
template<typename T>struct BIT{
	T c[N<<1];
	#define lowbit(x) (x&-x)
	inline BIT(){memset(c,0,sizeof(c));}
	inline void insert(int x,T v){
		for(;x<=M;x+=lowbit(x)) c[x]+=v;
	}
	inline T query(int x){
		T res=0;
		for(;x;x^=lowbit(x)) res+=c[x];
		return res;
	}
	inline void clear(){memset(c,0,sizeof(c));}
	#undef lowbit(x)
};
BIT<int> T1;
BIT<ll> T2; 
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='G') p[++m]=i;
		pre[i]=pre[i-1]+(s[i]=='G');
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j+=2)
			if((pre[j]-pre[i-1])&1) ans--;
	p[0]=0,p[m+1]=n+1;
	for(int k=1;k<=m;k++){
		for(int l=p[k];l>p[k-1];l--)
			for(int r=p[k];r<p[k+1];r++)
				if(((r-l+1)&1)) ans+=abs((l+r)/2-p[k]);
		T1.clear(),T2.clear();
		ll num=0,val=0;
		for(int i=k-1,j=k+1;i>=1&&j<=n;i--,j++){
			T1.insert(p[i]+p[j],1),T2.insert(p[i]+p[j],p[i]+p[j]);
			num++,val+=p[i]+p[j];
			for(int l=p[i];l>p[i-1];l--)
				for(int r=p[j];r<p[j+1];r++){
					if(!((r-l+1)&1)) continue;
					ll numl=T1.query(l+r),vall=T2.query(l+r);
					ll numr=num-numl,valr=val-vall;
					ans+=numl*(l+r)-vall;
					ans+=valr-numr*(l+r);
					ans+=abs((l+r)/2-p[k]);
				}
		}
	}
	for(int k=1;k<m;k++){
		T1.clear(),T2.clear();
		ll num=0,val=0;
		for(int i=k,j=k+1;i>=1&&j<=n;i--,j++){
			T1.insert(p[i]+p[j],1),T2.insert(p[i]+p[j],p[i]+p[j]);
			num++,val+=p[i]+p[j];
			for(int l=p[i];l>p[i-1];l--)
				for(int r=p[j];r<p[j+1];r++){
					ll numl=T1.query(l+r),vall=T2.query(l+r);
					ll numr=num-numl,valr=val-vall;
					ans+=numl*(l+r)-vall;
					ans+=valr-numr*(l+r);
				}
		}
	}
	put('\n',ans);
	return 0;
}

详细

Test #1:

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

input:

GHHGGHHGH

output:

12

result:

ok single line: '12'

Test #2:

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

input:

HHHHHHHHGHGGHGGGGHGGGHGGHGGHGGGGHHHHHGGGGHGHHHGGHGGHHGGHGHGHGHGHGHHHGGHHGHGGHGGGHGGGGHHGGHHHGHHGHHGG

output:

98047

result:

ok single line: '98047'

Test #3:

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

input:

GGHHHGHGHHHHGHHHHGHGHGGHHHGHGGHHHGGHGHHGGHHHHGGGHHGGGGHHHGGHGHGHHHGGGGHHHHGGGGGHGHGGGHGGGGHHHGHHHHGGGHGGGHHGGHGHHHHHHGHHHHGGHGHHGHHGHGHHHHHHHGGGHGGHGHGHHGHGHGHHHHGGHGHHGGHHHHGHGHGGHGHHGGHHGHGHHHGGHGHG

output:

1377709

result:

ok single line: '1377709'

Test #4:

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

input:

HGGHGHGGGHHHHGGHHGGHHGGHHGHHGHHGHHHGGGGHHGGGGHGGGHGHGHHHGHGGGHGGHHGGGHGHHHHHGHGGHHGHGHGHGHGHHHGGGHGHGGGGHHHHGGHHGHGGGGHHGHGHHGGHGGGHHHHHGGHGHGHGGHGGHHHGHGGHGHHHHGGHHHHGGHHHHHHGGGHHHGGGGHHGGHGGGGHHGHHHHGHGGGGHGHHHHHHGGGGGGGHHGHHHHGGHGHGGHHHHHHHHHGHGGGGHHGGGGGGGHHGHGHHGHHGHGHHHGHHGGGHHGGGGGHGGHGHHHGGH...

output:

18589853

result:

ok single line: '18589853'

Test #5:

score: 6.25
Accepted
time: 19ms
memory: 3704kb

input:

GHGHGHGHHGGHGGHGHGHGHHGGHHHHHGGGHHGHHHGGHHHHHHHHGHHHHHHGHGHGGHGHGHHHGHGGHGHHHHHGHHHHHGGGHGHHGHGGGGGHHGHGGGHGGGGGHHGHGGHHGGHGHHHGHHHGGHHGHHHHHGGGGHHHHGGGGHGGHHGHHGHHGGGHGHHGHGGGGGHHGHHHHHGHHHHHHGHGGHHHGGGHGHGHGHGHHHGGGGGHHHGHGGHHGGHGGHGHGHHGHGGGHGGGGGGHHHHGGGHGHGGHHGGGHHGGHGHHHHGGGGHGGGHGHGGHHGGGGHGG...

output:

239620295

result:

ok single line: '239620295'

Test #6:

score: 6.25
Accepted
time: 67ms
memory: 3620kb

input:

GHGHHGHHHHHHHGHHGGHHGGHHHGGHHHGGGHHGHGGGHHGGGHGHGHGGHHHHGGGGHGGHHGGHGHHHGGGHHHGHGHHGHHGGHGGGGGHHHHGGGGHGHHHHHGGHGGGGGHGGHHHHGHGHGGHGGGGGGGGHHHGGHHHHGGHHHHGHGGGGHGGHHHHHHHHGGGHHGHGHHHGGGHGHGGGHHHGGHHHGHHHHHHGHGHGHHGHHGHGHHHGHHGGGGHGHGHHGHGHHHGGHGGGGGHGGGHHHHGHGHHHHGHHGGHHHHGHGGHHGGGHGHGHHGHHGHGHHGGGG...

output:

3749745269

result:

ok single line: '3749745269'

Test #7:

score: 6.25
Accepted
time: 351ms
memory: 3612kb

input:

HHHHGGHHHHHHHHGGGHHGHHGHGGHHHGHHGHHHGGGHHHHGHGGGGHGHGGGGHHHHHGHHHGHGHGGGGGGGGHHGHHGGHGHGGGGGHGGHHHHGHHGGHGGHHGGHHGGHGHGGGGHHHGGHGGGHHGGHGGGGGHHHHGHHHGHGGGGGGHGHHHGGHHGHGHHHHHHGHGGHGGHGHGHGGGHGHGHHGHGHGGHGHHHGHGHGHGGHGGHHGHHHGHGGGGGHGGHHHGHHGGGHHGGGHGGHHHHGHHHGGGHGHGGGHGGHGGGHHGGHHGHHHHGHHGHHHGGHHGHH...

output:

81813329996

result:

ok single line: '81813329996'

Test #8:

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

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHGHHHHHHHHHHHGHHHHHHHGGHHHHHHHHHHHHH...

output:

1993575766369

result:

ok single line: '1993575766369'

Test #9:

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

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHGHHHHGHHHHHHHHHHHHHHHGHGHHHHHHHHGHHHHHHGHHHHHHHHHHHH...

output:

1936319118814

result:

ok single line: '1936319118814'

Test #10:

score: 6.25
Accepted
time: 304ms
memory: 3788kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHGHHHGHHHHHHHHHHHHHHHHHHHHHHH...

output:

1906624646754

result:

ok single line: '1906624646754'

Test #11:

score: 6.25
Accepted
time: 292ms
memory: 3608kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHGHHHHHHHHHHHHHHHHHHHHHGHGHHHHHHHHHHGHHHHGHHHHHGHGHHHHHHHHHHHHHHHH...

output:

2056784748165

result:

ok single line: '2056784748165'

Test #12:

score: 6.25
Accepted
time: 770ms
memory: 3504kb

input:

HHGHGHHGHGHGGHGHGGHGGHHGGGGGGGGGHGHGGGGHHGHGGHGGHGHGGGGGGHGGHHHGHHHGGHGHHHGGHHGGGHHHGGHHGGHHHGHGHHHHHGHGHHHHHGHGGGGHGHHHHHGHHGHGHHHHHGGGGGHGHHGGHGGGHHGHGGHGHHHHGHHGHHHGGHHGGGGGGHGGHHHGHGGHHGGGGHGGGGHHGGHHGGHGGHGGGHHHGGHGHGHGHHGGHGHGGGHHHHGGGHHGHHGHHHHGHGGGHHGHGGGGHHGHHGHHHGHGHHHGHHGGGHGHGHHHHHGHGGGH...

output:

516066376178

result:

ok single line: '516066376178'

Test #13:

score: 6.25
Accepted
time: 656ms
memory: 3764kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHHGHHHHHHHHGHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9878475549129

result:

ok single line: '9878475549129'

Test #14:

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

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH...

output:

9918848392027

result:

ok single line: '9918848392027'

Test #15:

score: 6.25
Accepted
time: 685ms
memory: 3540kb

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGGHHHHHHHHHHHHHHHGHHHHHHH...

output:

9882416063183

result:

ok single line: '9882416063183'

Test #16:

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

input:

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHGHHGHHHH...

output:

9847097832382

result:

ok single line: '9847097832382'