QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#608865	#7814. 消消乐	XuJunMing	100 ✓	45ms	31024kb	C++14	616b	2024-10-04 08:26:34	2024-10-04 08:26:35

Judging History

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

[2024-10-04 08:26:35]
评测

测评结果：100
用时：45ms
内存：31024kb

查看

[2024-10-04 08:26:34]
提交

answer

#include <bits/stdc++.h>
using namespace std;
char s[2000005];
stack<char>st;
unsigned long long p[2000005]={1},now;
const unsigned long long base=257;
int n;
long long ans;
unordered_map<unsigned long long,int>mp;
int main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	scanf("%d%s",&n,s+1);
	mp[0]=1;
	for(int i=1;i<=n;++i)p[i]=p[i-1]*base;
	for(int i=1;i<=n;++i){
		if(!st.empty()&&st.top()==s[i]){
			now-=p[st.size()]*st.top(),
			st.pop();
		}else{
			st.push(s[i]);
			now+=p[st.size()]*st.top();
		}
		ans+=mp[now]++;
	}
	printf("%lld\n",ans);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 5

Accepted

time: 0ms

memory: 3876kb

input:

10
aaaaaaaaaa

output:

result:

ok single line: '25'

Test #2:

score: 5

Accepted

time: 0ms

memory: 4144kb

input:

10
ooooppuuhh

output:

result:

ok single line: '16'

Test #3:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

10
nnppkkppjj

output:

result:

ok single line: '16'

Test #4:

score: 5

Accepted

time: 0ms

memory: 4144kb

input:

10
vvcckkhhqq

output:

result:

ok single line: '15'

Test #5:

score: 5

Accepted

time: 0ms

memory: 4136kb

input:

10
llmmxxoopp

output:

result:

ok single line: '15'

Test #6:

score: 5

Accepted

time: 0ms

memory: 4184kb

input:

800
jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjddzziiyyyyjjooppiivvppmmooppttnnbbmmaaqqvvkkllyyvvmmjjsswwxxccwweeeekkhhaakkvvffaaiieessmmiibbff...

output:

result:

ok single line: '38306'

Test #7:

score: 5

Accepted

time: 0ms

memory: 3888kb

input:

800
pffpgppguqqugllgwhhwxjjxpkkpxnnxlkklunnuxiixallayqqyccccjnnjnyynqccqqjjqtuutboobwddwfwwfgvvgwuuwpqqppttpyggysrrsgwwgeddexbbxbssbvbbvbeebweewwkkwwddwnoontddtcddcajjapffptcctkeekboobfjjfvaavpjjpriirlfflnazdsevmozgezlngnhktrllcgorjoollwtqylmmzxfeibnifcebsnnugzluzlizievzxfnlokzodymigextlmyltzbmptyjf...

output:

result:

ok single line: '27479'

Test #8:

score: 5

Accepted

time: 1ms

memory: 4244kb

input:

8000
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

result:

ok single line: '3820477'

Test #9:

score: 5

Accepted

time: 1ms

memory: 3972kb

input:

8000
neenbnnbvjjvddddommolrrlzttzqwwqlfflijjiaqqayaayihhiqmmqduudlzzlyzzyannatyytfiifbqqbroorcffcgjjgwhhwoqqopuupdjjdeqqewnnwvwwvpiiprqqrukkuhbbhsiisrqqrxvvxfmmfzkkzjlljimmiazzariirdvvdcuucpaapbaabbaabccccxqqxivvipttpqffqmggmzhhzdaadyxxyhccheddeaiianggnxjjxqssqfaafqllqskksfuufviivozzocwwcznnzfxxfnss...

output:

result:

ok single line: '2713693'

Test #10:

score: 5

Accepted

time: 1ms

memory: 3980kb

input:

8000
ivviurrukrrkaccafoofaxxaleelcyycsiisimmifvvfoeeodppdneenqjjqsccsguugonnoyiiymttmcjjcmkkmjwwjieeikeekdbbdolloyvvyolloxiixmaamfnnfzrrzqbbqweewvttvboobbeebcmmcsqqsiyyifddfyvvyvttvvddvejjeeeeeleellzzlzbbzcrrcobbowsswquuqozzoyqqyulluwvvwyxxyxllxwrrwgmmgeppecvvcsiisyvvyukkuyppyryyrhjjhthhtvssvvnnvnee...

output:

result:

ok single line: '2721590'

Test #11:

score: 5

Accepted

time: 23ms

memory: 14628kb

input:

200000
tdaatgfvypbdkxdlvttiuksoooxszoqnqvmtznizlqfstlenqrnmdpkmvhmzftporwzvlbpyplrvrkgrpvqxyjcwwpcinilarbaudodadcglszflkzvmmdahgqphqoueltddqlymwpvweslymviccsmhuezesmlwsswgznaofullpxciuezrbkxfnodiglhpyrfcjajyuqzfoxsysgeqrqmvtqysypgaivfetwhmgxngzdvavbkipanoopqftdmntwpxgaljiqrkppywfuspzfgljheckapftjqar...

output:

result:

ok single line: '8356'

Test #12:

score: 5

Accepted

time: 28ms

memory: 14680kb

input:

200000
nleqrvpkpopfbstnolidsxrfhivbwbbqbwxmvymzmnwozrbklbuwliccquzhpfjsbxlnkzewvjpjarqmwcpsvovxeynjrgdjxrauincbnjvokawliinjqqulwxxeztpbrotihuiyjjqsxxosragocxbpjmhquczgwfakfaojxslteazikjqkebpcrrggswjiyetkpyvjubhtoounhveftykvetuwqgpddicnarbsigpjytmhcymvapbmkforkaeccsuhmwiuljmvajlztzjghnohlmxnmdehfxnra...

output:

result:

ok single line: '8340'

Test #13:

score: 5

Accepted

time: 4ms

memory: 5912kb

input:

200000
abbabbbbbbaababaaabaaaababaaaaaabbababababbabbaaababbbbaabaabbbbbbababaabababbababaabbaabaaaabbbbbaabbbbaababbbabaaababbbbbbbbbbabbbabaabaabaababbbbbbabaabbbbbbbbbbaaabbbbabaabbaababaaabbabbaaabbbbbaaabababaababbaaabbbbababbbbbbaaaabaaaaaaabbbaabbaaaabbabbbbbaabbbbbbbabbaaaabaaabaabbaaaababbb...

output:

52315097

result:

ok single line: '52315097'

Test #14:

score: 5

Accepted

time: 0ms

memory: 5600kb

input:

200000
aaaababaaaaabbabababbbbabbbbababbabbaabaaabbabbaabaaaaaabaaaabbbbbbbabaabbabaabababbbaabbbbabbbbbaabaaaabaaaababaaaabbaaaaabbbabbbabbbbbbbaabbbabbaaabbbabaabaaaaaaaaababbaaabbbbaabaabbaaababbabbaabbbbaaababbbbbbbbbbbaabaaabbaaabaabbaaabbabaabbabbaabbbababbaaabaaaaaabbbbbbbabaabbabbaabaabaabaa...

output:

72221142

result:

ok single line: '72221142'

Test #15:

score: 5

Accepted

time: 0ms

memory: 6644kb

input:

200000
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

2395581278

result:

ok single line: '2395581278'

Test #16:

score: 5

Accepted

time: 0ms

memory: 6344kb

input:

200000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

2396621459

result:

ok single line: '2396621459'

Test #17:

score: 5

Accepted

time: 0ms

memory: 6356kb

input:

200000
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

2395864064

result:

ok single line: '2395864064'

Test #18:

score: 5

Accepted

time: 42ms

memory: 31024kb

input:

2000000
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

239586659381

result:

ok single line: '239586659381'

Test #19:

score: 5

Accepted

time: 45ms

memory: 30844kb

input:

2000000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

239687303822

result:

ok single line: '239687303822'

Test #20:

score: 5

Accepted

time: 44ms

memory: 30856kb

input:

2000000
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

239608981171

result:

ok single line: '239608981171'