QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99646#6265. PareidoliaScintilla100 ✓515ms91464kbC++142.5kb2023-04-23 11:17:212023-04-23 11:17:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-23 11:17:25]
  • 评测
  • 测评结果:100
  • 用时:515ms
  • 内存:91464kb
  • [2023-04-23 11:17:21]
  • 提交

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;
}

詳細信息

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