QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#103060 | #6265. Pareidolia | ZSH_ZSH | 0 | 12ms | 9028kb | C++14 | 1.1kb | 2023-05-04 10:06:29 | 2023-05-04 10:06:33 |
Judging History
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: ''