QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31745 | #21644. 基因序列问题 | expeca# | 100 ✓ | 138ms | 37868kb | C++ | 2.6kb | 2022-05-12 09:54:25 | 2022-05-12 09:54:26 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=500010;
int sz,last,go[N][4],len[N],diff[N],link[N],series_link[N],baby[N];
int n,m,i,j,k,x,y,f[N],bit[N];
int ans[N];
vector<pair<int,int> >poses[N],que[N];
char s[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
inline int go_until_pal(int i,int v){
while(s[i]!=s[i-len[v]-1])v=link[v];
return v;
}
inline pair<vector<int>,vector<int> >add_char(int i){
last=go_until_pal(i,last);
int&v=go[last][s[i]-'a'];
if(v==-1){
v=sz++;
len[v]=len[last]+2;
if(!last)link[v]=1;
else{
last=go_until_pal(i,link[last]);
link[v]=go[last][s[i]-'a'];
}
diff[v]=len[v]-len[link[v]];
if(diff[v]==diff[link[v]]){
baby[v]=baby[link[v]];
series_link[v]=series_link[link[v]];
}else{
baby[v]=v;
series_link[v]=link[v];
}
}
last=v;
pair<vector<int>,vector<int> >ans;
for(int u=v;u!=1;u=series_link[u]){
int B=baby[u];
vector<pair<int,int> >&vec=poses[B];
int left=i-len[u]+1;
if(vec.size()&&vec.back().first==left)vec.back().second=len[u];
else vec.push_back(make_pair(left,len[u]));
ans.first.push_back(i-len[B]+1);
if(vec.size()!=1){
int L=vec[vec.size()-2].first,
len_=vec[vec.size()-2].second,
R=L+len_-1,
L_=R-len[u]+1;
ans.second.push_back(L_);
}
if(vec.size()!=1)if(vec[vec.size()-1].second==vec[vec.size()-2].second){
vec[vec.size()-2]=vec[vec.size()-1];
vec.pop_back();
}
}
return ans;
}
inline void add(int x,int p){for(f[x]+=p;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
int main(){
scanf("%s%d",s+1,&m);
n=strlen(s+1);
for (int i=1;i<=n;++i){
if(s[i]=='A')s[i]='a';
if(s[i]=='G')s[i]='b';
if(s[i]=='C')s[i]='c';
if(s[i]=='T')s[i]='t';
}
sz=2,last=0,len[0]=-1;
for(i=0;i<=n+5;i++)memset(go[i],-1,sizeof(go[i]));
for(i=0;i<m;i++){
read(x),read(y);
que[y].push_back(make_pair(x,i));
}
for(i=1;i<=n;i++){
pair<vector<int>,vector<int> >vec=add_char(i);
vector<int>adding=vec.first,deleting=vec.second;
for(j=0;j<deleting.size();j++){
if(!f[k=deleting[j]])continue;
add(k,-1);
}
for(j=0;j<adding.size();j++){
if(f[k=adding[j]]==1)continue;
add(k,1);
}
for(j=0;j<que[i].size();j++)ans[que[i][j].second]=sz-2-ask(que[i][j].first-1);
}
for(i=0;i<m;i++)printf("%d\n",ans[i]);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 16ms
memory: 27236kb
input:
CCAAAACAAACACAGAGGAAACAACAACCAGCATAAACACTCAGTAAAACACGAGCACAGGAAAAAGAGAACCAGCCTCCAAAAAACAAACGCAGCACAAACTGCACCAACCGAAACAACACAACCGAAAATCCCAGTCAGGCAAGACACCAAACACGACAAACCAACACAAAAACCTACCAACACACACCAAAAACACAAAGGCTGAAAAACGACCGACCCCGCACGACAACAACAACCAAGAGACGAACCAACAACTAAACACCCAGCACGAACAAAAAACACAAGACCCCAGAAAAA...
output:
160 127 429 102 318 21 506 326 333 368 45 299 316 22 268 268 352 233 432 414 260 407 269 233 115 365 378 423 481 341 222 329 228 371 193 517 386 305 255 117 120 189 41 99 434 301 121 186 364 200 53 420 493 353 340 268 286 236 354 341 156 154 392 308 397 385 339 109 417 377 440 406 406 264 503 518 17...
result:
ok 6500 numbers
Test #2:
score: 10
Accepted
time: 11ms
memory: 27724kb
input:
GCCCCCACCAAACCAAATCAAACTAGCACAACCAAAAAAATACAGAACGAACACAGAAAAAACAGGAAAAACAAAGAAACGAAACCCAGTACATAAGGGATAAAAACAAGAAACGAAACCCACAAGAGCAGAAGCAAAAAAAAAACCCACACCTTAAACCCCACACCAACAAAAGCACACAAACACAACACGACCCCCTGAGGAGTAAGCCTCAAAACAACGAACCCAACTCGGAAATCAATATGAAAAAACACCGGAGCACCTCACGCCACAACACCCGAGAAAATCACGCGACCAACC...
output:
338 299 374 501 204 495 447 356 268 397 269 271 138 644 195 110 238 127 516 356 507 289 476 579 477 399 317 234 512 335 401 497 497 162 463 607 109 458 246 321 147 456 147 459 320 228 428 349 317 115 653 582 386 653 229 401 636 201 358 126 425 304 195 513 245 106 437 294 565 445 503 410 114 519 619 ...
result:
ok 23000 numbers
Test #3:
score: 10
Accepted
time: 8ms
memory: 27756kb
input:
AAACAAGCCAACAAGGACGCCAAAAGCACGCAATACAAGACCACCTGACAAACGAAAACTAACCAAACAGCACGAAAACAGACAAGGAACACAAGGAGAACAAGAAGATAACAAAAACTAGAAAAAAACACCATAACAGCATGCAAAACACAAACCCAAAACAAAAACTTAACAAAAAAAAGACAAGGGCCCACAAAAACAACAAAAAAAACCTCCTGAACAACCGCGGACAACCCGACCCACGCGCGCCCGGACCAACCAAACAAACTAAACCAGAACCCCCCCCGCGCAAAACCAACA...
output:
313 480 40 641 460 365 378 550 314 212 532 358 187 519 288 251 171 573 280 345 223 429 590 328 99 593 337 111 441 310 168 441 157 160 181 382 477 560 445 318 293 631 38 588 385 600 434 163 406 509 298 642 340 384 271 428 52 176 503 514 227 306 51 236 465 349 48 240 251 388 233 462 371 336 402 232 17...
result:
ok 23000 numbers
Test #4:
score: 10
Accepted
time: 22ms
memory: 27808kb
input:
AAAAAAACCACACACGAAGCAACGACACATCCAAACGAAAAAAAACAGAAAAGATTAACTCAAAACCAAAAACAAACCAGAGAAGGGGACAGGTAACCGAAATTAAACCCCTGCAACCCAAGCAAAAAAAACCCATACACCCCAGAAGCAAACAAACAGAGAAAGACAACCAGGCGAACTAAAAGAAAAAAACACAACCGGATCAGAACCACACTAAAGCCACCATCAACCGGCCGCGCAAACAAAGCAGCAACAACCACAATAACCATAACAAAAGAAGTAAATACCGCGGCAACAAAA...
output:
8 527 316 672 460 568 178 640 399 355 607 418 207 126 349 376 575 516 589 559 613 484 106 585 402 355 271 447 331 158 154 454 305 316 234 269 454 438 177 567 645 270 443 386 203 386 20 175 29 431 316 214 476 229 236 250 482 384 328 530 516 227 543 217 428 271 212 157 263 691 531 569 591 552 548 496 ...
result:
ok 23000 numbers
Test #5:
score: 10
Accepted
time: 43ms
memory: 30916kb
input:
AACGCACACATTGAAAAAACACCCCACAAAACGAAACATAAAAAGCGAACAATGACCTCAGAAACAGATACGGAAACAGCCAACGCCAGAACAAACCACATACCCCAGCCGAGAATCGAAAATAGCCACCTCAATGGACCGAACTAGCCACACACGACGAGGCAAGGCAAGAATGAGGCTGGATACCACGAAACTACCCTCAAACCAGACCACCAGCAAACACAGCGCACGAGACAGGGCAGAACACAGCTCCCAAAAACGGCACACGAGCAGATGGCCCAACCACCAAAAAAAAATAGA...
output:
40 230 114 113 161 152 70 168 208 167 131 172 254 19 181 275 125 165 146 137 179 182 170 77 54 208 129 158 90 63 220 90 132 192 86 156 230 234 187 204 34 214 49 202 260 173 149 206 161 155 174 149 123 165 66 101 260 73 5 132 124 101 109 196 38 67 155 17 229 61 186 173 94 150 256 30 237 240 166 62 17...
result:
ok 230000 numbers
Test #6:
score: 10
Accepted
time: 22ms
memory: 29112kb
input:
GCAGAACAGGGAAATGCACCCGCCCCCACAACCACCACACACCAGAACTAAGTCTAAACTGGAGAATACAAAACCCCGAAACAATGCGTCCAACAAGCAGCAAAACGTATACGACAACCAAACACACAAACAGAGCCACAACTAAAAACGCAGAACTCAACAATGACCAACAACAACCACCAAATCGACAGAATACAAAAACAAAAAAAAACAACCCAAAAAAGAATCGCAAAAAAAGAAATCCAACCGGCCGAAAAGCAGCCCAGCAACACGAGAACAACCACCCCAACAGAAACCCAA...
output:
294 372 874 406 533 191 349 606 892 302 860 489 205 588 786 740 824 642 838 635 352 660 521 582 80 431 849 720 457 692 312 726 397 912 245 523 786 423 652 706 272 619 489 475 200 932 612 909 725 530 668 38 443 25 728 771 295 135 226 315 556 270 466 851 622 62 488 522 950 768 604 733 531 695 761 188 ...
result:
ok 50000 numbers
Test #7:
score: 10
Accepted
time: 25ms
memory: 29076kb
input:
AACAGCCGACAACAGATACAAAGGGAACAAAAGAGTCCAACAACCCAAACCACAGCACAAAATGAAAACAAACAGAAACCGAACGACTCAATCTCACAAGGATAGAGAGACGAAACGGGCGCCAACAAATACCCTACAAAAGAAAACAAAGCCTGGACGCAAAGAACACACACAAAGAGAAAAGAAAACTCACCAACAGGACAAGAAAACAAAAACACAGCACCCGGAACCAAACCATACAAGGCAACAAACAAGCACCCGCGAAAAATACGACGTCACGGAAAAACAACAGACCCCAAC...
output:
891 683 695 883 726 578 188 706 829 777 712 221 457 932 973 833 270 735 899 515 156 708 550 500 38 475 548 629 243 487 141 341 221 831 398 444 961 921 633 536 512 249 599 195 629 736 701 884 601 513 324 218 332 772 650 668 343 359 603 446 300 570 293 288 282 441 557 683 649 747 575 417 229 394 800 7...
result:
ok 50000 numbers
Test #8:
score: 10
Accepted
time: 138ms
memory: 37840kb
input:
TAAACAAAAGGCAGACAGACACACACGAGAAGAAGAACGGTCGAGAAGAAAGCGCCTACAAAACCCACAGACCCGGACACTACAAAGATACAGAAACAAGCGCGAAACAGAACAAAGAAACACAAACCCAGCCCAAAACACAGAATCAAAGGTCAGCTAAAACACGCAAGCTCAACGCAAAAACCAAACCAGTAAATCCAACAACAAATATGGAAAACCCCAGAACAGCAACAACCCTCGGAAATAGCCCATGCCGCCCTTCAAAGAAAAGAACGATAAGAAAGAGTAGCCCAATAAAGA...
output:
767 1690 464 1446 530 937 525 1214 513 1085 1928 1741 1465 1119 676 410 299 1569 236 1273 1953 1263 1033 1308 1120 1005 1869 827 1413 1412 1176 1354 1734 1163 1865 1245 1277 667 625 668 1652 1199 1596 483 43 774 1590 674 1676 1471 1311 735 870 931 1798 553 1960 1791 930 1167 1067 696 248 916 503 674...
result:
ok 230000 numbers
Test #9:
score: 10
Accepted
time: 124ms
memory: 37760kb
input:
ACCCACCACCGCGAGGAAAAACACAACCAAAACAACGGCGTCCACAAACGACACGCGAGACAGCACAAGAACAAAAGCCAAGACAGAACAGCTAAAAAACGACTATAACCAACAATCAACCCACACAACACAAAAAAGCCACGAGAAAAGACAACCCCAACCCAATAGACAACACCACCCACAAAAGACCGAACAAGAACAAAAGACCCAACGCAACCAAAGACCAAATGTAACCATGGAAAACATTCAGAACAGATAAAAAAATAAACAACATACAGAAGCAAGACAAACCAACCCCAT...
output:
1398 860 964 664 1224 909 215 690 1476 742 942 1018 264 977 1422 699 1044 478 1487 758 1711 1967 769 721 1001 780 1496 990 1960 1591 1451 855 318 189 1276 608 1841 1333 1000 928 1645 1002 1681 369 1529 1646 1300 1754 1253 1469 794 1048 897 1836 1612 550 1090 1663 649 1781 1998 1608 1633 1453 1114 84...
result:
ok 230000 numbers
Test #10:
score: 10
Accepted
time: 123ms
memory: 37868kb
input:
CGACAACAGACAAAGAAAACCAAAATTCAAACCCACGACCAAACAAAACAACACAAACGCCACCAATAACGCGCGATCACACAACCAAAACGCCAGACTAAAACCAAAATATTATAAGCACCAAAACCACGACCGAAACCGGACCCGGAAGGGAGAACCAAGCAACACTAACATACACTAAAAGCAAAACAAAGCACAAACACCAAAACAACAAACCCACAGTAGCATAAAACTAAGCACAACGGAAAGACCAAACCGACCCTCGAAGATAACCAAGCACCACCCAGGCAATCGAACCCA...
output:
2001 1563 1367 1849 1364 1504 1461 1232 415 1526 480 1080 398 224 1416 331 859 1448 1561 1444 515 1435 1275 1504 571 1486 1766 1375 631 2013 382 1759 1819 1439 684 515 588 1332 974 819 910 1311 1249 631 1684 879 471 655 1081 1556 267 1073 1410 712 801 2016 597 712 1172 880 933 903 1662 1150 350 1996...
result:
ok 230000 numbers