QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103060#6265. PareidoliaZSH_ZSH0 12ms9028kbC++141.1kb2023-05-04 10:06:292023-05-04 10:06:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-04 10:06:33]
  • 评测
  • 测评结果:0
  • 用时:12ms
  • 内存:9028kb
  • [2023-05-04 10:06:29]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	string s; cin>>s; int n=s.size(); s=" "+s;
	
	unordered_map<int,int> mp;
	vector<int> p{1,2,3,3,4,2};
	vector<array<int,5> > nxt(n+2);
	
	mp['b']=1,mp['e']=2,mp['s']=3,mp['i']=4;
	rep(i,0,4) nxt[n+1][i]=n+1;
	drep(i,n,0)
	{
		nxt[i]=nxt[i+1];
		nxt[i][mp[s[i]]]=i;
	}
	
	vector<ll> t(n+2);
	auto lowbit=[&](int x){return x&(-x);};
	auto update=[&](int x,ll y){while (x<=n) t[x]+=y,x+=lowbit(x);};
	auto getsum=[&](int x){ll res=0; while (x) res+=t[x],x-=lowbit(x); return res;};
	auto query=[&](int l,int r){return getsum(r)-getsum(l-1);};
	
	rep(i,1,n) update(i,1);
	
	ll ans=0,lst=0;
	rep(i,1,n) if (s[i]=='b')
	{
		int cur=i-1;
		for (auto x:p)
		{
			if (cur==n+1) continue;
			cur=nxt[cur+1][x];
		}
		if (cur==n+1) continue;
		ll v=query(lst+1,i);
		ans+=v*(n-cur+1);
		update(cur+1,v);
		lst=i;
	}
	cout<<ans<<endl;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3396kb

input:

bessiebessie
3
3 l
7 s
3 s

output:

14

result:

wrong answer 2nd lines differ - expected: '7', found: ''

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3476kb

input:

bebesxsxesebssxeseisssxsesbebsibssbeexxsseeeiesxeebbsbebsbibebebbieexeeebebbbxbsisbbsxxbsssxbeebiisesiissbxseeseixxiexbeiebsieexesssisssssebsxbxisisxibsiseseeiibxxisixxsissebesebsiiseixxesebsxsisixibi
200
187 s
37 x
27 s
102 s
11 x
179 x
177 x
63 s
129 i
124 x
69 e
160 b
17 e
95 x
114 s
187 e
35 x
1...

output:

35731

result:

wrong answer 2nd lines differ - expected: '35731', found: ''

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 8976kb

input:

jbelypjxsrooewvccrucqssirjxzzcviugeblmeontdtwdnsaubeztxodptqcyqtsiesgvybifgrwecjrgsuvbrjlrxncawswsxcitfwbeayxpzytqbduivnebklewsefeerndeeqyvrfvpmssjebffinzejgebgugbdhledtqdcmsaxpftajysvruewpumqvlcbixgemnybdgnhzpmjgebrydxnbsubsoxntwsktooqnieddbehumcropjnrbsusxbmwszkawqessjdshorvoqiwljfqeqghhpbavtqgokb...

output:

11511979939906

result:

wrong answer 2nd lines differ - expected: '11511979939906', found: ''

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 8992kb

input:

xppcryeedlunuzsdbqyzbjpzeoswosxcakrizrziyqezxkvrrdlbmfkoxhesysuidebkgbuefukenfompasbkysynxostwqcuuamygeilrfmgobdvkndmezjbrnnyedeuspoxvkwnrsimdvdstukypihsyhecemgmdfbbbfsviwiepowupsjpbusqrqiwoikpzfefpausgotloibrzkvzeqadnmrejupwsnbhussocrrnpyswthsvztbifetbphezsltsibgezbwebsewndstolspqnixehmbbuzgdeqbmbl...

output:

16114703742716

result:

wrong answer 2nd lines differ - expected: '16114703742716', found: ''

Test #5:

score: 0
Wrong Answer
time: 10ms
memory: 8988kb

input:

bjesiisxywyieblgsehiseadsytzfsembqpikkjyhjaxhbvweqpbeepvmpcsnousljsvbuueikqkbmvfretmuigilnewmadfxjvweokjhnkimybgzgderygunegsrshhvzkfhnjsklgsveennkkqdvvmyratbqfpbqizesviitsasjebongxmhekqfosasdytitqjaqsfylscuzjcipbwhkemesguoybzcletspnsmpoiyieccyegmnixdpbaotzbzukwdqebuxatcwzcfoezrsupctwyrgaavevgjseiebk...

output:

10284970992982

result:

wrong answer 2nd lines differ - expected: '10284970992982', found: ''

Test #6:

score: 0
Wrong Answer
time: 2ms
memory: 6112kb

input:

eebxsxeeseisixbbexeixeiixiieeixieesxseebsexexebxssbeebsxbsbeexxssiieixsisebisebexxsbesebessseeiseesssxssbbibesxsexebxssiseexiiebseseeibxexexxseexbsebseexesbiebseibissisissxebebixieeisiebibxexeixxxsxbbbseeeeixeeeebxxssbsbsssessbsesexesxssbxeexbeisseexesixseesseesxbieexsebssesixbebssxeeesesxebxsxebbxx...

output:

6022249971561

result:

wrong answer 2nd lines differ - expected: '6022249971561', found: ''

Test #7:

score: 0
Wrong Answer
time: 8ms
memory: 6064kb

input:

xxssiiebsxexsieeeseebixsbbbssisebesxbbseeeissxeiesebxbeebbssxssebbssxesxibessxsseeibebsesissessbixssbxbisbisibisxbxxssxxiseseesxesbeeseeesebibeessexesxixeibebixxexisxexbssssxbbissseesesebiseexeesxeisisixebxexxeeeisseisbsbesxbibbebsesbxseiixsixibeexseeesebeieiieesiieisxixeiisxssexsixbsxssssbbbxeissss...

output:

5914383755236

result:

wrong answer 2nd lines differ - expected: '5914383755236', found: ''

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 6128kb

input:

iebseexibsieissbsseesbsiesisssieieisibssexbxebxisesebseexeexeeiiessexexbeibsbeeisebseieebbssissbxsbseexxeisibsisissbxxbbseesebbexbebexiseeseseebesebsiexiieseeebieexisibeebeessxseiiisesxbbeeixsssbxisesbisbbesssxssbbebisseieiesexsxsbxssseiesibbsebsebbxbiesebxxeixieeesbisesiesiebxxxsisxsebxsxsebeessese...

output:

5920756014928

result:

wrong answer 2nd lines differ - expected: '5920756882586', found: ''

Test #9:

score: 0
Wrong Answer
time: 7ms
memory: 6068kb

input:

eesexbxxsisexesissseseiibssxxeieeeieeeixsiiesesesbsseibsbeeixesseieebesesisbissexesssibeessexseesbseeeeieseebxbxessxieibeexsesxsebessisssxeeesxeibxsebesexxibsiesxxsxsbsxsesesiessexseseeiesxxeesexbisesieebsbsbbsebesbeebeesbssebibseeiibeseixxxsbibsbeseieexsbxieibiebeississiesxesieiissxsssesbssibieeise...

output:

5966167021111

result:

wrong answer 2nd lines differ - expected: '5966167150451', found: ''

Test #10:

score: 0
Wrong Answer
time: 1ms
memory: 6068kb

input:

issessbssxssxxsesexxeseexsesseixssexexbiibxsseiisebissibiexxsiessebseeexixeibssxiixsebebisxsseexbsbsebbbsxeieiexxbibebiebsssieixsbsiixesieixsxessbxbiixeeessbeeexsixixsexexiebsbxeesbesbbeessxsesesbeexesbbsxeibsexebxsxiieibseisbbieebiissxssxxeeebxsssexexxxbsexbessexsxsssbiexisbixbibiisississxsexeiexxs...

output:

6019636313148

result:

wrong answer 2nd lines differ - expected: '6019636795913', found: ''

Test #11:

score: 0
Wrong Answer
time: 3ms
memory: 6040kb

input:

bsesesesisexbxssbeesexseisseixbsxiesiessxsieesseissxeiixisssiebbsbeeesxbxixseexissbsseessisibsiesbxesixseebisbssxsxesiesxseiseeeebsseseesbssbsexsbxssssesbxseebbeeexiibsexexbssbeisbsiisiebesssisxexeiissseesbxeexsexxixesxbexsibeeexebeiesesebsbssssieexxeexebixebeiisebssxeibbbsesxxeebibeseesbbsebeeieexe...

output:

5973592969011

result:

wrong answer 2nd lines differ - expected: '5973592969011', found: ''

Test #12:

score: 0
Wrong Answer
time: 7ms
memory: 6112kb

input:

esxseeeeesexesssisiseisexssbssebssbiessebsssbxixsebesissiibexssseeeesessxxixxixeseeseseeexxexbibsxbisbssibexieebeisxxeixbiseiisissbxibeexissiexeesisxbbeiexeeexseiixeiesbssssibexsesxxsbsxeixissessiseebeseisxxsbeexesxibiissbsixseesibsbsxsssssseiebibeesexxeseeeebbsisieeebsxxiibieesssebbxesbbxsbxsexixss...

output:

5904649218997

result:

wrong answer 2nd lines differ - expected: '5904649218997', found: ''

Test #13:

score: 0
Wrong Answer
time: 3ms
memory: 6112kb

input:

eeeseeesssssisssexseesxssesssbiisbbexeesssesxsbbeesesiseiixiibxixsebxebsbesbbesxsexiessbsxessebeixeeissbxbeissxbsebebsebxxssesxsesxxsibeebssssixxeesbxxisiexissxsiesisisexsxxsebiieexbeiiissessbieesssssebexesxxxsibesssxeeesieieeeisseixxseiieeisexbbssiibesebexbisisbbxisxbesibssxeeibexeieesxsbesiiesbsxe...

output:

5952492499136

result:

wrong answer 2nd lines differ - expected: '5952492499136', found: ''

Test #14:

score: 0
Wrong Answer
time: 6ms
memory: 8828kb

input:

ssxebsseeisexxeeseesiisbieebsiibseebeeessxeebbbsexsbbseiseesssxsbeiiseeesxesxbixxeexxiixsseesiixibeexsxebeseebexsxesebsxiisbxsxsixiisbexeixbsesxexxieexeeisxexexsebxesssbiessbieiisesseesesssiexesxseessibsxeeeibeesxsxesexxesesibexsiiiieessesxxxisiisisexeieibeiibixiesesseiseesbbebbeseibsieesesbbebeiisx...

output:

47358168602672

result:

wrong answer 2nd lines differ - expected: '47358168602357', found: ''

Test #15:

score: 0
Wrong Answer
time: 12ms
memory: 8964kb

input:

eixbbessxbexssebxibsxibeissxexbsbsiseiissesbbxbsiesixbbebieebseesisexeesisxsxxisssssxexxessxebesxbbxibeixsssessxseixbeexxiexixesssbebseebbxbsssbeeieessexsxebeiessiexbbeeiesbbsxseessebixxssessbbexbsebbssibsixsexbxisxseixbssssibeibeebsesissxbbeeebsxeeesexbbibsiisxeiiesxssxssesssxeexeeexsieesxeeebeesee...

output:

48164214436806

result:

wrong answer 2nd lines differ - expected: '48164214436806', found: ''

Test #16:

score: 0
Wrong Answer
time: 12ms
memory: 8976kb

input:

eibbxsesebsessieebbxexxiebxsbibxsseixebeeibbxsssxsesiebissbbexsxxieeibxebesxieeeeixsexeeeebiesessexibeissessieeesexieiebsbsebbiisiieeeeesxieeebexssesebesesbssxsesxiiessisebseeexsexebieseeeeessbsiessseeibxesebsbbxsixesiibsbssxsssxxxxebsxibsbxxseixxixxeessissseexsiexbieixsisssseesseissbsseeseiseexssxe...

output:

48172629727254

result:

wrong answer 2nd lines differ - expected: '48172629727254', found: ''

Test #17:

score: 0
Wrong Answer
time: 12ms
memory: 9024kb

input:

ssxexebsisibxissixxsisxxieseisibsissibxbsessxsxesbebbiieiibeixxxixixebeesbxiseeiesebsssseeeesbseexibsesssibxibsseisexssxxbxseesisbebieesisbbxxsbiexeexseseeieeisssisisxsbeixisixesiebssxesxseexexsssxsebeieibeeisbbeiieeiexixsxbisesseiessbeeesesxeiseiesixsexbisesieissbebesbsbiexeeesebixiebesixxbxseiixee...

output:

48005670254873

result:

wrong answer 2nd lines differ - expected: '48005670254873', found: ''

Test #18:

score: 0
Wrong Answer
time: 12ms
memory: 8992kb

input:

xsbxbieiiebssseeesessieiissessebbixseeisebbseebeexxexeexexissssixxibxiiieeeieseebebixebessebsbbsxseiebsssxbsisbsixeeeexxsxsssxeieesbbebibebsseexsbisiiisesbssiexebiixeiseesibibieesexssissexsixebeseseissibesbeiisbeeibbiiesbxxeesessesebbeesebissesesxxsexxsibseisebeesxexesssxeexeeexxissxxesisexssesbbeeb...

output:

47215163711382

result:

wrong answer 2nd lines differ - expected: '47215164049607', found: ''

Test #19:

score: 0
Wrong Answer
time: 8ms
memory: 8984kb

input:

xebesxsssssibiiseeexibxxxisbeessxeseeiixssxsxeexiesxieiisssxseieisseieesixeeeibssbseixssessssxsxsexseesixiiiesbxebebbsbsiseebbeeeebsessxbsssesbsesssxeiexesseixbbsexebeexsxssxxeebxeebeeexebsxssexeseesseibeeiiisxxsiieeeiseexxisxssssbbiissseessexiexeeeeseisebxbiebexxxeeieixeesesebsbbieiebsxxsebsxeixxei...

output:

47344242090851

result:

wrong answer 2nd lines differ - expected: '47344242090851', found: ''

Test #20:

score: 0
Wrong Answer
time: 4ms
memory: 9028kb

input:

sbsieesxiesiiesexiisebsxbsssebsebexesesxbisxsixsssbeeexeesbeexsiixeexseebbesxesxsxxeeexbebbesssbixbbbeibeebxxxeeeseixsiseisibbseeisbsssbxbsbeseexseebseeissxessxbsisebbseeexseiebsebsesexibsessexebbeexessesbsxxssseesesieeisiesieeisssxebexbeixbsesissxeisxebesxxsesssexiieesssssxbebsssxsesxbesbxisisbesex...

output:

47465694182169

result:

wrong answer 2nd lines differ - expected: '47465694182169', found: ''

Test #21:

score: 0
Wrong Answer
time: 6ms
memory: 8860kb

input:

ebibexssisbssxxseissxsixeesebessiseesxbsbibseeiiesxieebbsieexeisexexbxebissssbsiseixsxbeesibsxssxsesseesessissxeeixebsbisbsbbeeisissesxexsesbsxbsxxisieeseiesxesiiiesbssebexsisisesxsbsxexessieesxbxesseebsexxeesxessxbibsxsebixeebsesxsisiesbiseebsxsbsesixeieesxeeesesxxssxbxbesbssbxseixeexssseeebieesexi...

output:

47712559653222

result:

wrong answer 2nd lines differ - expected: '47712559653222', found: ''