QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99646 | #6265. Pareidolia | Scintilla | 100 ✓ | 515ms | 91464kb | C++14 | 2.5kb | 2023-04-23 11:17:21 | 2023-04-23 11:17:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
using u32 = unsigned int;
using i64 = long long;
const int N = 2e5 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int n;
char str[N];
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid (l + r >> 1)
u32 cl[N << 2][6], cr[N << 2][6], sl[N << 2][6], sr[N << 2][6], x[N << 2][6], y[N << 2][6];
i64 dat[N << 2];
void down(int u, char c) {
rep(i, 0, 5) {
cl[u][i] = cr[u][i] = 0;
sl[u][i] = sr[u][i] = 0;
}
dat[u] = 0;
rep(i, 0, 5) {
x[u][i] = (i + (c == "bessie"[i])) % 6;
y[u][i] = (i == 5) && (c == 'e');
}
cr[u][x[u][0]] = 1, sr[u][x[u][0]] = y[u][0];
rep(i, 0, 5) cl[u][i] = 1, sl[u][i] = y[u][i];
}
void maintain(int u) {
rep(i, 0, 5) {
cl[u][i] = cr[u][i] = 0;
sl[u][i] = sr[u][i] = 0;
}
dat[u] = dat[ls] + dat[rs];
rep(i, 0, 5) {
cr[u][i] += cr[rs][i];
cr[u][x[rs][i]] += cr[ls][i];
sr[u][i] += sr[rs][i];
sr[u][x[rs][i]] += sr[ls][i] + cr[ls][i] * y[rs][i];
cl[u][i] += cl[ls][i];
cl[u][i] += cl[rs][x[ls][i]];
sl[u][i] += sl[ls][i];
sl[u][i] += sl[rs][x[ls][i]] + cl[rs][x[ls][i]] * y[ls][i];
x[u][i] = x[rs][x[ls][i]];
y[u][i] = y[ls][i] + y[rs][x[ls][i]];
dat[u] += 1ll * sr[ls][i] * cl[rs][i] + 1ll * cr[ls][i] * sl[rs][i];
}
}
void build(int u, int l, int r) {
if (l == r) return down(u, str[l]), void();
build(ls, l, mid), build(rs, mid + 1, r);
maintain(u);
}
void modify(int p, char c, int u, int l, int r) {
if (l == r) return down(u, c), void();
if (p <= mid) modify(p, c, ls, l, mid);
else modify(p, c, rs, mid + 1, r);
maintain(u);
}
#undef ls
#undef rs
#undef mid
int main() {
scanf("%s", str + 1), n = strlen(str + 1);
build(1, 1, n);
printf("%lld\n", dat[1]);
for (int m = read(); m; -- m) {
int p = read();
char c = getchar();
while (!islower(c)) c = getchar();
modify(p, c, 1, 1, n);
printf("%lld\n", dat[1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.7619
Accepted
time: 2ms
memory: 15848kb
input:
bessiebessie 3 3 l 7 s 3 s
output:
14 7 1 7
result:
ok 4 lines
Test #2:
score: 4.7619
Accepted
time: 0ms
memory: 15852kb
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 35731 35731 35731 36187 36187 35143 35143 38299 38299 37298 37298 37298 37298 37298 43766 44114 43649 43649 43649 43649 43649 43221 43149 37383 37383 37383 44268 44268 44378 44529 42878 42878 42878 42878 43371 43371 43371 37791 37298 37034 37034 37034 37034 37272 39414 39414 39307 39307 39313 ...
result:
ok 201 lines
Test #3:
score: 4.7619
Accepted
time: 21ms
memory: 91464kb
input:
jbelypjxsrooewvccrucqssirjxzzcviugeblmeontdtwdnsaubeztxodptqcyqtsiesgvybifgrwecjrgsuvbrjlrxncawswsxcitfwbeayxpzytqbduivnebklewsefeerndeeqyvrfvpmssjebffinzejgebgugbdhledtqdcmsaxpftajysvruewpumqvlcbixgemnybdgnhzpmjgebrydxnbsubsoxntwsktooqnieddbehumcropjnrbsusxbmwszkawqessjdshorvoqiwljfqeqghhpbavtqgokb...
output:
11511979939906 11511979939906 11511979939906 11511979939906 11517041213977 11517041291002 11517041291002 11517041291002 11517041291002 11517041291002 11517042196313
result:
ok 11 lines
Test #4:
score: 4.7619
Accepted
time: 21ms
memory: 91080kb
input:
xppcryeedlunuzsdbqyzbjpzeoswosxcakrizrziyqezxkvrrdlbmfkoxhesysuidebkgbuefukenfompasbkysynxostwqcuuamygeilrfmgobdvkndmezjbrnnyedeuspoxvkwnrsimdvdstukypihsyhecemgmdfbbbfsviwiepowupsjpbusqrqiwoikpzfefpausgotloibrzkvzeqadnmrejupwsnbhussocrrnpyswthsvztbifetbphezsltsibgezbwebsewndstolspqnixehmbbuzgdeqbmbl...
output:
16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716 16114703742716
result:
ok 11 lines
Test #5:
score: 4.7619
Accepted
time: 22ms
memory: 90860kb
input:
bjesiisxywyieblgsehiseadsytzfsembqpikkjyhjaxhbvweqpbeepvmpcsnousljsvbuueikqkbmvfretmuigilnewmadfxjvweokjhnkimybgzgderygunegsrshhvzkfhnjsklgsveennkkqdvvmyratbqfpbqizesviitsasjebongxmhekqfosasdytitqjaqsfylscuzjcipbwhkemesguoybzcletspnsmpoiyieccyegmnixdpbaotzbzukwdqebuxatcwzcfoezrsupctwyrgaavevgjseiebk...
output:
10284970992982 10284970992982 10284970993346 10284970993346 10284971464442 10284971464442 10284973046372 10284973046372 10284973046372 10284973046372 10284973046372
result:
ok 11 lines
Test #6:
score: 4.7619
Accepted
time: 189ms
memory: 55772kb
input:
eebxsxeeseisixbbexeixeiixiieeixieesxseebsexexebxssbeebsxbsbeexxssiieixsisebisebexxsbesebessseeiseesssxssbbibesxsexebxssiseexiiebseseeibxexexxseexbsebseexesbiebseibissisissxebebixieeisiebibxexeixxxsxbbbseeeeixeeeebxxssbsbsssessbsesexesxssbxeexbeisseexesixseesseesxbieexsebssesixbebssxeeesesxebxsxebbxx...
output:
6022249971561 6022249971561 6022250641419 6022250641419 6022250411949 6020823612699 6020823612699 6020823612699 6020823612699 6020823612699 6020823612699 6020823612699 6020823612619 6020823975803 6020823975803 6020824070903 6020824070903 6020824070903 6020824070903 6020824070903 6020824070903 602082...
result:
ok 100001 lines
Test #7:
score: 4.7619
Accepted
time: 164ms
memory: 55748kb
input:
xxssiiebsxexsieeeseebixsbbbssisebesxbbseeeissxeiesebxbeebbssxssebbssxesxibessxsseeibebsesissessbixssbxbisbisibisxbxxssxxiseseesxesbeeseeesebibeessexesxixeibebixxexisxexbssssxbbissseesesebiseexeesxeisisixebxexxeeeisseisbsbesxbibbebsesbxseiixsixibeexseeesebeieiieesiieisxixeiisxssexsixbsxssssbbbxeissss...
output:
5914383755236 5914383755236 5916862644004 5916862644004 5916862644004 5919169480654 5919169480654 5919169480654 5919168882392 5919169038704 5919168890664 5919168890664 5919168890664 5919168890664 5919169146499 5919169146499 5919169146499 5919169146499 5919169203667 5919169903743 5919169632183 591916...
result:
ok 100001 lines
Test #8:
score: 4.7619
Accepted
time: 182ms
memory: 56772kb
input:
iebseexibsieissbsseesbsiesisssieieisibssexbxebxisesebseexeexeeiiessexexbeibsbeeisebseieebbssissbxsbseexxeisibsisissbxxbbseesebbexbebexiseeseseebesebsiexiieseeebieexisibeebeessxseiiisesxbbeeixsssbxisesbisbbesssxssbbebisseieiesexsxsbxssseiesibbsebsebbxbiesebxxeixieeesbisesiesiebxxxsisxsebxsxsebeessese...
output:
5920756014928 5920756882586 5920756882617 5920756882617 5920756882617 5920756882617 5920756882617 5920756882617 5920756934921 5920756934921 5920756934921 5920756934921 5920756934921 5920756934921 5920757055069 5920757578089 5920757578089 5920757578089 5920757578209 5920757578209 5920755156188 592075...
result:
ok 100001 lines
Test #9:
score: 4.7619
Accepted
time: 181ms
memory: 56768kb
input:
eesexbxxsisexesissseseiibssxxeieeeieeeixsiiesesesbsseibsbeeixesseieebesesisbissexesssibeessexseesbseeeeieseebxbxessxieibeexsesxsebessisssxeeesxeibxsebesexxibsiesxxsxsbsxsesesiessexseseeiesxxeesexbisesieebsbsbbsebesbeebeesbssebibseeiibeseixxxsbibsbeseieexsbxieibiebeississiesxesieiissxsssesbssibieeise...
output:
5966167021111 5966167150451 5966167150451 5963810812414 5963810812414 5963810812401 5963810702775 5963810759715 5963810759715 5963810840352 5963810840352 5963811354250 5963811354250 5963811354346 5963811354346 5963811354346 5963811354346 5963811354346 5963811354346 5963811354346 5961522649246 596152...
result:
ok 100001 lines
Test #10:
score: 4.7619
Accepted
time: 176ms
memory: 56632kb
input:
issessbssxssxxsesexxeseexsesseixssexexbiibxsseiisebissibiexxsiessebseeexixeibssxiixsebebisxsseexbsbsebbbsxeieiexxbibebiebsssieixsbsiixesieixsxessbxbiixeeessbeeexsixixsexexiebsbxeesbesbbeessxsesesbeexesbbsxeibsexebxsxiieibseisbbieebiissxssxxeeebxsssexexxxbsexbessexsxsssbiexisbixbibiisississxsexeiexxs...
output:
6019636313148 6019636795913 6019636795913 6019636795913 6019636795889 6019636795869 6019636369234 6021069585543 6021069585570 6021069585570 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021069546345 6021070148765 602107...
result:
ok 100001 lines
Test #11:
score: 4.7619
Accepted
time: 180ms
memory: 55884kb
input:
bsesesesisexbxssbeesexseisseixbsxiesiessxsieesseissxeiixisssiebbsbeeesxbxixseexissbsseessisibsiesbxesixseebisbssxsxesiesxseiseeeebsseseesbssbsexsbxssssesbxseebbeeexiibsexexbssbeisbsiisiebesssisxexeiissseesbxeexsexxixesxbexsibeeexebeiesesebsbssssieexxeexebixebeiisebssxeibbbsesxxeebibeseesbbsebeeieexe...
output:
5973592969011 5973592969011 5973592969533 5973592221445 5973592079853 5973592079853 5973592079853 5973592355649 5973592355649 5973592641378 5973592482852 5973592482852 5973592526565 5973592526565 5973593339468 5973593339468 5973593339468 5973593339468 5973593102676 5973593102676 5973593102676 597359...
result:
ok 100001 lines
Test #12:
score: 4.7619
Accepted
time: 185ms
memory: 55640kb
input:
esxseeeeesexesssisiseisexssbssebssbiessebsssbxixsebesissiibexssseeeesessxxixxixeseeseseeexxexbibsxbisbssibexieebeisxxeixbiseiisissbxibeexissiexeesisxbbeiexeeexseiixeiesbssssibexsesxxsbsxeixissessiseebeseisxxsbeexesxibiissbsixseesibsbsxsssssseiebibeesexxeseeeebbsisieeebsxxiibieesssebbxesbbxsbxsexixss...
output:
5904649218997 5904649218997 5902999012569 5902999012569 5902999012569 5902998730497 5902998730497 5902999068441 5902999068441 5902999532291 5905383128311 5905383128311 5905383128311 5905383128311 5905383128183 5905383128183 5905383128183 5905383128183 5905383128183 5905383128147 5905383128147 590538...
result:
ok 100001 lines
Test #13:
score: 4.7619
Accepted
time: 177ms
memory: 56812kb
input:
eeeseeesssssisssexseesxssesssbiisbbexeesssesxsbbeesesiseiixiibxixsebxebsbesbbesxsexiessbsxessebeixeeissbxbeissxbsebebsebxxssesxsesxxsibeebssssixxeesbxxisiexissxsiesisisexsxxsebiieexbeiiissessbieesssssebexesxxxsibesssxeeesieieeeisseixxseiieeisexbbssiibesebexbisisbbxisxbesibssxeeibexeieesxsbesiiesbsxe...
output:
5952492499136 5952492499136 5952492499136 5952492499136 5952491886224 5950238448880 5950238448960 5950238448960 5950238448960 5950238448960 5950238448960 5950238384467 5950238384467 5950916419121 5950916418857 5950916418857 5950916418857 5950916418857 5950916418857 5950916418857 5950916418857 595102...
result:
ok 100001 lines
Test #14:
score: 4.7619
Accepted
time: 450ms
memory: 88104kb
input:
ssxebsseeisexxeeseesiisbieebsiibseebeeessxeebbbsexsbbseiseesssxsbeiiseeesxesxbixxeexxiixsseesiixibeexsxebeseebexsxesebsxiisbxsxsixiisbexeixbsesxexxieexeeisxexexsebxesssbiessbieiisesseesesssiexesxseessibsxeeeibeesxsxesexxesesibexsiiiieessesxxxisiisisexeieibeiibixiesesseiseesbbebbeseibsieesesbbebeiisx...
output:
47358168602672 47358168602357 47358168602357 47349805599779 47349805957685 47349805957685 47349805957685 47349805957685 47349805957685 47349805957685 47349805957685 47349805791800 47349805791800 47349805791800 47340822471167 47340822471167 47340822471167 47340822082455 47340822082455 47340820244175 ...
result:
ok 200001 lines
Test #15:
score: 4.7619
Accepted
time: 441ms
memory: 89012kb
input:
eixbbessxbexssebxibsxibeissxexbsbsiseiissesbbxbsiesixbbebieebseesisexeesisxsxxisssssxexxessxebesxbbxibeixsssessxseixbeexxiexixesssbebseebbxbsssbeeieessexsxebeiessiexbbeeiesbbsxseessebixxssessbbexbsebbssibsixsexbxisxseixbssssibeibeebsesissxbbeeebsxeeesexbbibsiisxeiiesxssxssesssxeexeeexsieesxeeebeesee...
output:
48164214436806 48164214436806 48164214436806 48164214436806 48164214436806 48164214436806 48164214436806 48164213271360 48157101864900 48157102835345 48157103634441 48157103634441 48157104584631 48157104584631 48157104131861 48157104131933 48157104131898 48157104210368 48157104210368 48157104210368 ...
result:
ok 200001 lines
Test #16:
score: 4.7619
Accepted
time: 450ms
memory: 89092kb
input:
eibbxsesebsessieebbxexxiebxsbibxsseixebeeibbxsssxsesiebissbbexsxxieeibxebesxieeeeixsexeeeebiesessexibeissessieeesexieiebsbsebbiisiieeeeesxieeebexssesebesesbssxsesxiiessisebseeexsexebieseeeeessbsiessseeibxesebsbbxsixesiibsbssxsssxxxxebsxibsbxxseixxixxeessissseexsiexbieixsisssseesseissbsseeseiseexssxe...
output:
48172629727254 48172629727254 48172629580611 48172629580611 48172629580611 48172629580611 48172629580611 48165444253725 48165444505812 48168839043417 48168839043417 48168839043417 48168839043417 48168839043417 48168834911940 48168834911952 48168834911952 48165912273792 48165912273792 48165912273792 ...
result:
ok 200001 lines
Test #17:
score: 4.7619
Accepted
time: 469ms
memory: 87780kb
input:
ssxexebsisibxissixxsisxxieseisibsissibxbsessxsxesbebbiieiibeixxxixixebeesbxiseeiesebsssseeeesbseexibsesssibxibsseisexssxxbxseesisbebieesisbbxxsbiexeexseseeieeisssisisxsbeixisixesiebssxesxseexexsssxsebeieibeeisbbeiieeiexixsxbisesseiessbeeesesxeiseiesixsexbisesieissbebesbsbiexeeesebixiebesixxbxseiixee...
output:
48005670254873 48005670254873 48005670254873 48005670110041 48005670110003 48005669099028 48005669099028 48005669099028 48005669099028 48015307174462 48015307289194 48015304349899 48015304349905 48015304349905 48015304349905 48015304479124 48015304479124 48022909559572 48022913444992 48022913444992 ...
result:
ok 200001 lines
Test #18:
score: 4.7619
Accepted
time: 428ms
memory: 87648kb
input:
xsbxbieiiebssseeesessieiissessebbixseeisebbseebeexxexeexexissssixxibxiiieeeieseebebixebessebsbbsxseiebsssxbsisbsixeeeexxsxsssxeieesbbebibebsseexsbisiiisesbssiexebiixeiseesibibieesexssissexsixebeseseissibesbeiisbeeibbiiesbxxeesessesebbeesebissesesxxsexxsibseisebeesxexesssxeexeeexxissxxesisexssesbbeeb...
output:
47215163711382 47215164049607 47215163050042 47215163050042 47215163050105 47211022314319 47211022491399 47211022491393 47211022491393 47211022589253 47211022350849 47211022076028 47212095366996 47212095366996 47212095369146 47212096792604 47212095374564 47217230246507 47217230246507 47217230246507 ...
result:
ok 200001 lines
Test #19:
score: 4.7619
Accepted
time: 473ms
memory: 87500kb
input:
xebesxsssssibiiseeexibxxxisbeessxeseeiixssxsxeexiesxieiisssxseieisseieesixeeeibssbseixssessssxsxsexseesixiiiesbxebebbsbsiseebbeeeebsessxbsssesbsesssxeiexesseixbbsexebeexsxssxxeebxeebeeexebsxssexeseesseibeeiiisxxsiieeeiseexxisxssssbbiissseessexiexeeeeseisebxbiebexxxeeieixeesesebsbbieiebsxxsebsxeixxei...
output:
47344242090851 47344242090851 47344242090851 47344242540905 47344242540860 47344242596210 47344242596210 47344242596120 47344242514671 47344242514671 47344242514671 47344242514671 47344242557096 47353499330354 47353498096170 47353498096170 47353498124535 47353498124535 47353498124535 47353498124535 ...
result:
ok 200001 lines
Test #20:
score: 4.7619
Accepted
time: 515ms
memory: 88512kb
input:
sbsieesxiesiiesexiisebsxbsssebsebexesesxbisxsixsssbeeexeesbeexsiixeexseebbesxesxsxxeeexbebbesssbixbbbeibeebxxxeeeseixsiseisibbseeisbsssbxbsbeseexseebseeissxessxbsisebbseeexseiebsebsesexibsessexebbeexessesbsxxssseesesieeisiesieeisssxebexbeixbsesissxeisxebesxxsesssexiieesssssxbebsssxsesxbesbxisisbesex...
output:
47465694182169 47465694182169 47465694182169 47465696260713 47465696260713 47465696260713 47465696413434 47465695963082 47465696633654 47465696601659 47465696601659 47456155934089 47456155934089 47464268142986 47464268142986 47464268142986 47464268143042 47464268143042 47464268143042 47464268276152 ...
result:
ok 200001 lines
Test #21:
score: 4.7619
Accepted
time: 446ms
memory: 88484kb
input:
ebibexssisbssxxseissxsixeesebessiseesxbsbibseeiiesxieebbsieexeisexexbxebissssbsiseixsxbeesibsxssxsesseesessissxeeixebsbisbsbbeeisissesxexsesbsxbsxxisieeseiesxesiiiesbssebexsisisesxsbsxexessieesxbxesseebsexxeesxessxbibsxsebixeebsesxsisiesbiseebsxsbsesixeieesxeeesesxxssxbxbesbssbxseixeexssseeebieesexi...
output:
47712559653222 47712559653222 47712559716909 47712559716909 47712559716909 47712559997511 47712559997511 47712560109723 47712553894243 47712553894243 47712553894243 47712554591345 47712554591345 47712554591345 47712554591245 47712554591245 47712554591245 47712554591245 47712554591245 47712554591245 ...
result:
ok 200001 lines