QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259326 | #7748. Karshilov's Matching Problem II | ucup-team902 | AC ✓ | 668ms | 60076kb | C++20 | 4.0kb | 2023-11-20 20:22:36 | 2024-08-25 20:42:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define gc c=getchar()
#define r(x) read(x)
#define ll long long
template<typename T>
inline void read(T &x){
x=0;T k=1;char gc;
while(!isdigit(c)){if(c=='-')k=-1;gc;}
while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}
const int N = 1.5e5 + 7;
const int p = 1e9 + 7;
const int base = 137;
const int SIZE = 600;
int be[N];
int L[N];
int R[N];
struct Query{
int l, r, id;
inline bool operator < (const Query &a) const{
return be[l] == be[a.l] ? r < a.r: l < a.l;
}
}Q[N];
inline int sub(int a, int b){
return a - b < 0 ? a - b + p : a - b;
}
ll f[N];
ll g[N];
int lenl[N];
int lenr[N];
ll Ans[N];
ll ans;
int Lg[N];
int dep[N];
vector<int> son[N];
int ac[N][20];
void dfs(int x){
for(int i = 1; ac[x][i] = ac[ac[x][i - 1]][i - 1]; ++i);
for(auto &v: son[x]){
ac[v][0] = x;
dep[v] = dep[x] + 1;
dfs(v);
}
}
inline int find(int u, int v){
if(u <= v) return u;
for(int i = Lg[dep[u]]; ~i; --i){
if(ac[u][i] > v){
u = ac[u][i];
}
}
return ac[u][0];
}
inline ll solve(int l, int r){
ll ret = 0;
for(int i = l; i<=r; ++i){
ret += f[min(r - i + 1, lenr[i])];
}
return ret;
}
inline void addr(int l, int r){
ans += g[find(lenl[r], r - l + 1)];
}
inline void addl(int l, int r){
ans += f[min(r - l + 1, lenr[l])];
}
inline void Get(int x, int &i){
int l = R[x] + 1, r = R[x];
for(ans = 0; be[Q[i].l] == x; ++i){
if(be[Q[i].r] == x){
Ans[Q[i].id] = solve(Q[i].l, Q[i].r);
continue;
}
while(r < Q[i].r) addr(l, ++r);
ll t = ans;
while(l > Q[i].l) addl(--l, r);
Ans[Q[i].id] = ans;
l = R[x] + 1;
ans = t;
}
}
char s[N];
char t[N];
int w[N];
int Next[N];
int hashs[N];
int hasht[N];
int pw[N];
vector<int> ins[N];
vector<int> rem[N];
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n, m; r(n), r(m);
scanf("%s", s + 1);
scanf("%s", t + 1);
for(int i = 1; i <= n; ++i){
r(w[i]);
f[i] = f[i - 1] + w[i];
}
g[1] = w[1];
son[0].push_back(1);
for(int i = 2, j = 0; i <= n; ++i){
while(s[j + 1] != s[i] && j) j = Next[j];
if(s[j + 1] == s[i]) ++j;
Next[i] = j;
g[i] = w[i] + g[Next[i]];
son[Next[i]].push_back(i);
}
dfs(0);
pw[0] = 1;
Lg[0] = -1;
for(int i = 1; i <= n; ++i){
hashs[i] = ((ll)hashs[i - 1] * base + s[i]) % p;
hasht[i] = ((ll)hasht[i - 1] * base + t[i]) % p;
pw[i] = (ll)pw[i - 1] * base % p;
Lg[i] = Lg[i >> 1] + 1;
}
for(int i = 1; i <= n; ++i){
int l = i, r = n, ans = i - 1;
while(l <= r){
int mid = (l + r) >> 1;
if(hashs[mid - i + 1] == sub(hasht[mid], (ll)hasht[i - 1] * pw[mid - i + 1] % p)){
l = mid + 1;
ans = mid;
}
else{
r = mid - 1;
}
}
lenr[i] = ans - i + 1;
if(lenr[i]){
ins[i].push_back(i);
rem[i + lenr[i]].push_back(i);
}
}
multiset<int> S;
for(int i = 1; i <= n; ++i){
for(auto &x: ins[i]){
S.insert(x);
}
for(auto &x: rem[i]){
S.erase(S.find(x));
}
if(S.empty()){
lenl[i] = 0;
}
else{
lenl[i] = i - *S.begin() + 1;
}
}
for(int i = 1; i <= n; ++i){
be[i] = (i - 1) / SIZE + 1;
if(!L[be[i]]) L[be[i]] = i;
R[be[i]] = i;
}
for(int i = 1; i <= m; ++i){
Q[i].id = i;
r(Q[i].l), r(Q[i].r);
}
sort(Q + 1, Q + m + 1);
for(int i = 1, x = 1; i <= m; ++x){
Get(x, i);
}
for(int i = 1; i <= m; ++i){
printf("%lld\n", Ans[i]);
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 14344kb
input:
8 5 abbabaab aababbab 1 2 4 8 16 32 64 128 1 1 2 3 3 5 4 7 1 8
output:
1 3 3 16 38
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 14076kb
input:
15 4 heheheheehhejie heheheheheheheh 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 2 3 4 8 2 6 1 15
output:
3 13 13 174
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 107ms
memory: 41940kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
108147037823514 221878585246974 455339807727642 440286198422821 148115747906237 88695249853257 351159618462315 58850354020997 65824434822005 270158033672354 197732558443069 298193894693053 239511187032650 28139154231325 408380171835227 268053430937402 32417121185965 104813548228675 44074926058619 78...
result:
ok 150000 lines
Test #4:
score: 0
Accepted
time: 106ms
memory: 40884kb
input:
150000 150000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
528900815691571 112638556022185 514229554849356 2216206133639915 295388515578381 1658587138269057 652142121207636 166322478628783 490195029871161 1191292846892788 1468501126902703 487990867773908 55994169916421 568966315599642 2522992078581539 2339888502167342 2881203249819745 154700081279584 152537...
result:
ok 150000 lines
Test #5:
score: 0
Accepted
time: 110ms
memory: 41068kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
386150762496368 2769669390423140 1025785181073675 1707930121656247 332135612349048 113937878332307 1128519694119799 476402941643931 980441978140407 1004994648999517 676169371268202 2607965889355671 273766796671958 711480908011402 71754482763611 400453994282744 975387094872830 810536618300388 2229061...
result:
ok 150000 lines
Test #6:
score: 0
Accepted
time: 149ms
memory: 42892kb
input:
150000 150000 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
25254725752128652 23497896664383313 15195391464047263 41143572895791434 7513384536045842 8871310939247699 17423823866879881 14601201534396958 6203483865940624 24953281161800570 24776576029495768 1687640411226 31563282955464371 29947970968962218 1149303801639767 5806503923049299 11201332188941891 116...
result:
ok 150000 lines
Test #7:
score: 0
Accepted
time: 239ms
memory: 44196kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
4570597927951323 11761063519994765 289982253793476 15684854914181269 19579321543184889 459972639580770 15246459216963247 1833393949769247 22425556248999709 11209560100586843 2883954996867615 14371655418173335 29207399108721 5943079608253242 1664456073054861 27405606916506455 23082758946788297 381175...
result:
ok 150000 lines
Test #8:
score: 0
Accepted
time: 668ms
memory: 60076kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
5697498028074951 21822720964918437 11237472002329727 84315407720465773 32198634509153899 40728716039967676 5913555967331675 10487781019914529 270012821917938205 239347797488036653 216168445985667902 67452321725546144 457298584810665039 187789940805492303 46241700003064393 242312618101113 42260337439...
result:
ok 150000 lines
Test #9:
score: 0
Accepted
time: 114ms
memory: 41252kb
input:
150000 150000 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
20591954951726 12208904434175 7662625006262 27638144315127 14991794671504 12693360208820 11037771157715 4373484191175 19325903476164 26048068499431 5723213500221 37836285761904 44407448222078 17672607641771 18226179013226 25664535060427 6571081196245 7364255499121 31338586400498 6963750199271 362906...
result:
ok 150000 lines
Test #10:
score: 0
Accepted
time: 129ms
memory: 41232kb
input:
150000 150000 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
26679397939583 14744203186201 5444732298002 2682795720153 8097594477750 11849141088914 4460923379501 213037786838 16105345264171 9432794502217 7341906921155 175129395650 26090540252644 7939835388186 1974417753321 13404114384225 3350016113286 11461223687633 11253459438574 10536087601821 410458842950 ...
result:
ok 150000 lines
Test #11:
score: 0
Accepted
time: 49ms
memory: 15924kb
input:
1000 150000 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababba...
output:
14533294687 36404448099 4898807521 8311487449 101191999742 73649429237 64160767440 94533233142 11330483415 11891445585 32475987658 20881014384 19725249244 46562700910 8954411927 15493987162 95870286230 21115698529 2452671987 14439012748 11977731306 12229300727 74351907054 22843320780 40597085949 512...
result:
ok 150000 lines
Test #12:
score: 0
Accepted
time: 45ms
memory: 14264kb
input:
1000 150000 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababba...
output:
54399359946 51977853051 49357792746 110019851897 69572597913 15709337251 55079579625 23693208641 171669911 1351037076 76795212797 40916790174 98891460109 3646721871 18505243674 61205775419 75138278275 44089408535 5074434752 50936710571 136345768092 19271144823 46362641831 62317616153 37671155153 162...
result:
ok 150000 lines
Test #13:
score: 0
Accepted
time: 85ms
memory: 41228kb
input:
150000 150000 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...
output:
38772069365927 38538545381556 38743522830612 38518262255568 38627306791107 38755103769862 38514395190995 38435548368667 38617960233472 38622898369466 38889725443048 38186753347601 38497568337263 38450570197606 38842403793276 38762153954801 38493442696613 38782127536129 38449780600849 38538849423248 ...
result:
ok 150000 lines
Test #14:
score: 0
Accepted
time: 45ms
memory: 12540kb
input:
1000 150000 aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcdeaa...
output:
58046174517 12715251464 5723988017 161223697602 137002400916 30563623878 98934054385 59077629445 113925111785 28840565698 156244390553 77320878352 59683981982 127942734209 121145579565 87520380292 55236806101 2117874653 80900981342 31724248103 50230142282 711792462 83498404152 29926218182 8820224616...
result:
ok 150000 lines
Test #15:
score: 0
Accepted
time: 42ms
memory: 16532kb
input:
1000 150000 aabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcd...
output:
43966954106 63457970792 261177599185 84416298978 32467601340 158024435898 129927481955 29905035826 1663395309 262974056170 126552502741 3977985830 6794527980 134076085617 153168175752 20202212393 20413397242 263088231784 188742026136 2338731931 31903630853 144258078247 11137714967 22338312083 194691...
result:
ok 150000 lines
Test #16:
score: 0
Accepted
time: 182ms
memory: 42416kb
input:
150000 150000 aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcde...
output:
29914293876821 29388248888943 5520238628990 6509772252533 11376377552909 901817826019 13219593022192 23330308156488 33721084055601 10522195135985 1748546656146 1553205391001 15793344985123 33174193324692 26957558511532 8590975656478 7024857425105 14444339872596 2023167053405 5779413699241 2334817520...
result:
ok 150000 lines
Test #17:
score: 0
Accepted
time: 182ms
memory: 42904kb
input:
150000 150000 aabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaaba...
output:
51654672077087 18128065265954 10648077478275 24096372633749 33921372063966 52844542543234 19475889095501 49998404687384 30981572147127 53639263941544 7723904914977 3305784882722 36334815617245 36978590959883 39392351303785 33813693293258 7380058627592 17560621637115 9885403408272 14150106810987 2507...
result:
ok 150000 lines
Test #18:
score: 0
Accepted
time: 298ms
memory: 40800kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
813092418312696 1317798689473715 1315665465011076 2405711931597 356128071216857 204530268744615 796004029533782 2524560020845716 2142315805349726 1000649874336585 3110164476348575 2074236435764977 869887553468426 135346186547404 2107116066259453 1409642986095650 923200979353524 376619890608622 17975...
result:
ok 150000 lines
Test #19:
score: 0
Accepted
time: 295ms
memory: 42048kb
input:
150000 150000 aabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaab...
output:
891232692268242 180239781074503 762986955623910 2182769025630738 892305971824847 911080210251582 1273751943749997 1612958343425903 839270032556736 1812514937518138 2753082659282112 1273772162515030 1359136888087723 2843461425942221 1848164748961046 601261559736813 12298394517162 882181981558879 2969...
result:
ok 150000 lines
Test #20:
score: 0
Accepted
time: 308ms
memory: 43768kb
input:
150000 150000 aabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaab...
output:
1194619495572 795884372512504 1175435646771188 2302482629192344 582273726204212 2236317824765870 119988076211482 678581408764964 2101023153383665 888572706609489 186359125426424 1397048595862182 1317852784077245 190253063244 865232742049445 1491695395427100 640644116246476 1446530862350308 170011517...
result:
ok 150000 lines
Test #21:
score: 0
Accepted
time: 259ms
memory: 41816kb
input:
150000 150000 aabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaab...
output:
432981642389138 369819684910697 674517425239465 595536647891124 177569847795803 934205515438256 182914252110569 3453242346130 379689140841865 472465468653933 551405636497734 924788388701343 387440477848840 403148807711424 118166293104989 231069344260660 455187760837014 654856703426747 14126165707025...
result:
ok 150000 lines
Test #22:
score: 0
Accepted
time: 290ms
memory: 43660kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
139092615923852 319712839391046 39921108996632 236395672026301 709843083668671 541581333895491 670629605184988 359722149795181 1434679507168815 427767149417380 103440733252864 162815973876064 5616565642136 213571238193114 473655044673898 1319021925607968 176177858522467 1094307268000496 789182609618...
result:
ok 150000 lines
Test #23:
score: 0
Accepted
time: 263ms
memory: 44292kb
input:
150000 150000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
176449221404353 857960219930710 842692900572808 32011407408076 36679450185285 77449627797994 773227897058900 242672941287399 112572896349484 1084073090765193 935389071307684 242262854116272 965264314963252 374225801426478 148690698579830 245286364056781 147691073049337 81763003844687 414872147677601...
result:
ok 150000 lines
Test #24:
score: 0
Accepted
time: 205ms
memory: 43108kb
input:
150000 150000 aabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaab...
output:
75013838237868 17352127196790 18435593123029 59453124031842 69320849384091 17191835150296 10989209368636 11277496094302 49325334063534 82744384056372 50402212769634 77714097271276 24123534251919 1019327991978 9791176811923 45077398495657 16921358697596 46140159436459 87938135723225 51608242695868 31...
result:
ok 150000 lines
Test #25:
score: 0
Accepted
time: 84ms
memory: 42900kb
input:
150000 150000 aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcde...
output:
51790349532872 51552703284865 51639707133662 51628954389848 51326994357282 51147387034925 51562168321876 51361004657199 51615987780988 51345690787679 51558502009159 51512388090741 51446130081472 51424934077872 51530952726784 51279069272495 51541846195039 51394309708021 51769796479739 51763888860806 ...
result:
ok 150000 lines
Test #26:
score: 0
Accepted
time: 90ms
memory: 43756kb
input:
150000 150000 aabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaaba...
output:
62738378528854 63240671067048 63109049690268 62930670790665 63128608767817 63154802293548 62903396261226 62691791732034 63072061751599 62678124397165 62854013020354 62810678615003 62432901249359 63266969650539 62868527107508 62984054065050 63323413497572 62820153495436 63041526771718 63072294192161 ...
result:
ok 150000 lines
Test #27:
score: 0
Accepted
time: 93ms
memory: 42040kb
input:
150000 150000 aabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaab...
output:
3685101344356853 3731861367894955 3751688492773431 3669019277489784 3728136168414795 3700443850676449 3692047336864334 3726615337010498 3732580406955496 3725834831382755 3756946026212108 3694602003701867 3711037467753390 3728247898408812 3756521839127576 3719104067223059 3695348388710118 37078393026...
result:
ok 150000 lines
Test #28:
score: 0
Accepted
time: 83ms
memory: 34348kb
input:
140000 150000 fxyviddixxstasofjeupbirusknnatlsgfekhgstmobjultzbnwmjewbqbkytmhchesjazdroxqmttlkpqokolalnpsptkxmuzytkimsnlnestfrmhtpkbwaznvkzlkwrnffhnucjdgmqnyefpsphxuqyebnczbtvtuwlcarbwlgnyzwmzjfvqrmhxoksqkxjutlrpdlaoseppwtmdnyepfqfygmwidklhpmkmhfytnuryjpztgcdrnzuzpfghnkhfscdlilfhheqwfuvpvbbusgwkkfcj...
output:
149487386057 113862413777 134923719940 23972844956 47659718599 139322041316 103615068534 18033539404 123080750859 32686113656 5606831184 57587094874 140892925172 186120371655 43492728874 76110450160 33616517940 11400279908 24389732424 24320716400 13997903903 45968029724 169420809364 81943765124 1018...
result:
ok 150000 lines
Test #29:
score: 0
Accepted
time: 77ms
memory: 34536kb
input:
150000 140000 qbagrggaowomatohfbgfglmelgpqgaqucijajgdhahzbpkpbkdqjyahjdenjfshmwhagkyjjszwuuswgpftghjtaogfffprhfhjiuwoigccgljccfhaihzagxswwfwusgswgggvjgfkfsntadaeafwshehnjwqwjgzkhebcggdhdsaafwehnjjwxgjfatxenkawzggfgxaavhjjkiflslegagehhhlkhgfapywyohexgfsxgawhdwdvhikswhfujwkgfojyshurcjnjghkhjsapdaadlff...
output:
41516161172 46091924632 36038323677 32196508911 19063468322 26836664454 13365203988 4215343027 16603596694 26910364649 6231712322 22129521478 34864597882 3182673144 60064960957 3130370755 17022957794 2006692899 31573229932 41465818542 37099154716 784864665 7224205839 41188101845 14389274943 25328998...
result:
ok 140000 lines
Test #30:
score: 0
Accepted
time: 3ms
memory: 16176kb
input:
1000 1000 yaaaaaaaaaaaagcaaaawbaawvaanaatptaaavakbaapmaqpmaaaameliakuaaaaaaafaaagaaaaaaaamalmajzakaacaaaiqqsfaaaaaamaaaaaajsaoajndafaaxahsaeaohqaoaaaaakmuqaaaayaaemalaamdaajaswaahawazaaaaakbgaaaqvaaiaabaniarauqaauamasadaaacxuazazaacaalapfaauaaalaaaavaaazaaaeacaaaaaxcalanaayzbxaaasalaasascaaaiaojaoav...
output:
370947276 234083642 402828548 15940636 81279372 0 452226648 0 0 15940636 386887912 97220008 0 81279372 0 81279372 15940636 15940636 686310290 234083642 386887912 81279372 81279372 386887912 234083642 686310290 702250926 234083642 386887912 152804270 605030918 15940636 686310290 97220008 686310290 15...
result:
ok 1000 lines
Test #31:
score: 0
Accepted
time: 83ms
memory: 35308kb
input:
150000 150000 jaapljaaadaaanasaeaaoaognyaatmgalaaaaajxaiahbaaauaauaairmyafhaoadaaaaaaaqaaeuaaacaaaueaaadaaaaaaaaqaaaaaaawacmraaaahapataaafmaaaaaxyahaazaajaalauhaatataibaayrhrxsmdsagaaaummymaaahmuaaaaaaaaaroxaayayaowtatyiaqvuahaoraavaaaaaacaaeaaearsdaafnajapaaaazaaaakcaazauladadnawaacazadeaaajahuiaqa...
output:
22819398310 24739907040 8629836374 23359395577 25736223491 15601539213 337784025 26174757748 11031343766 13328039385 10599601370 4093075630 13617636157 19709610870 3695394555 59620636021 43913032248 6612358951 13591313025 54649080650 19363465811 53924566117 21631188613 56653211225 32260240456 188007...
result:
ok 150000 lines
Test #32:
score: 0
Accepted
time: 95ms
memory: 43696kb
input:
150000 150000 abaaaaaaaabaaaaayaaaaaaaaaaabaaaaaaaaaaaaaaxaaaaaabaaaaabxaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaaaaaaayaaaaaazaaaaaaaaaaaaaaaaaaaaayaaxaaaaaaaaxaaaaaaaaaaaaaaaaaaayazaaaaaaaaaaazaaayaaaaabaaaaaaaaaaaaaaxaaaazaaazaayaaaaaz...
output:
2109154320691 1811295536184 1305874457798 1317480361367 3346830806215 1128585436673 2216669793859 876865837240 86073235223 298200815338 643988134846 1222094437721 2957947755668 362298850167 1482640156064 8210951856 1241506533511 1772927272097 215982589051 3107347387217 1316468548824 592284705655 435...
result:
ok 150000 lines
Test #33:
score: 0
Accepted
time: 35ms
memory: 15376kb
input:
1000 100000 abaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaaba...
output:
74798182608 157149465127 2105912190554 7460151149192 2268723395246 785956239210 435305709 2139278991147 1940216181949 88942985436 2872764543 2641374260497 400109478286 9690480277 2520126745257 341835162638 48689008059 25869193402 1079663008688 1652926212032 60415582650 5275716859677 46261753181 6122...
result:
ok 100000 lines
Test #34:
score: 0
Accepted
time: 30ms
memory: 12856kb
input:
1000 100000 xyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxy...
output:
149618841838 127864948561 54980335836 2543732655737 29119803604 111349757 2906360068619 89391907823 18211368590 501376038870 204593996945 311948130943 2532217668941 131848782598 514249430797 1064992254691 4007581664 1281829072352 2401926804764 537641132330 1985460140773 4940514023 1158980874786 2899...
result:
ok 100000 lines
Test #35:
score: 0
Accepted
time: 34ms
memory: 15368kb
input:
1000 100000 qisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqis...
output:
21743525132 2955679216579 142037109397 2808408913 183591971539 6035807926 1494265886855 111297641344 1751001849910 3192836139804 327654195802 1160271229172 155937740395 1233464278387 1071083667110 1413311998306 2362202307428 481043470961 855655615673 544719653451 1169701118795 340343809683 326585994...
result:
ok 100000 lines
Test #36:
score: 0
Accepted
time: 510ms
memory: 51892kb
input:
150000 100000 ppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppp...
output:
5592411450636753 135209829168391 49971109943102794 53150618284444849 32780298792197527 19668912700554961 3991295085690853 18121009996940124 1958502246040 348589459090434 6776793053734199 12667221050171100 71564981250810601 18728832441138479 14622207012817546 3781076536750452 699462977097104 43814745...
result:
ok 100000 lines
Test #37:
score: 0
Accepted
time: 500ms
memory: 48808kb
input:
150000 100000 tuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuutut...
output:
6029367874134384 14727991674637894 65528086805063 22262151197411199 13290008685433206 2216964586470248 35406020927137844 1288253206474488 122891953188100 15264445721996291 29769592090200819 54137147358694338 7064714568738187 13410090337383781 627494366583965 13119401523472213 18180772800585677 52023...
result:
ok 100000 lines
Test #38:
score: 0
Accepted
time: 495ms
memory: 50480kb
input:
150000 100000 eeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeove...
output:
660831893107150 852808508854170 25640865201842134 25858072792291872 61941952435199838 908296187754135 2190825954865481 12616603141014603 82649938049438 19574710854186724 18034029154050399 1743413410707578 1357830351826691 314778001830398 13442605730145814 34098282799367830 1152318337535 958861617983...
result:
ok 100000 lines
Test #39:
score: 0
Accepted
time: 580ms
memory: 49052kb
input:
150000 100000 ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
165193773150972023 1538088247569916 4077205028456474 64723160256828206 2879737616493342 13988682177623338 1022122245821095 47170492343166 69608730493211757 1084502483630793 563841093144006 13869016628394731 47897597658524539 88684322723491811 144432621254952409 117406025890040120 102915388576218776 ...
result:
ok 100000 lines
Test #40:
score: 0
Accepted
time: 545ms
memory: 45916kb
input:
149997 100000 abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabca...
output:
67598779861293222 36679538821933591 97698919357542782 15562591771418340 150553368460367 36980407863203108 4721746574275749 19110290707850782 107878608681437900 7604576038087844 7454079795245705 2408114454060810 200597787236533 751653612398308 12704990794626612 38180346177625555 14678791090778118 113...
result:
ok 100000 lines
Test #41:
score: 0
Accepted
time: 73ms
memory: 45120kb
input:
150000 100000 abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdab...
output:
138815215004022364 136361480020059660 137825902967695584 136313477499374331 134936003862446073 138149079107680312 137718268796572322 138746298238989081 137514238486868146 137549472707128014 134700961073280182 136494453652604168 136681098339708958 138400088399748010 138344288809278195 136485214236642...
result:
ok 100000 lines
Extra Test:
score: 0
Extra Test Passed