QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#480423 | #21648. Runs | KnownError_# | 100 ✓ | 437ms | 49456kb | C++14 | 1.9kb | 2024-07-16 15:31:47 | 2024-07-16 15:31:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n) for(int i=0;i<(n);++i)
#define sizc(x) ((int)(x).size())
#define allc(x) (x).begin(),(x).end()
#define fir first
#define sec second
constexpr int N = 1e6+5;
int n;
string s;
ull h[N],pw[N];
ull gh(int l,int r){return h[r]-h[l-1]*pw[r-l+1];}
int lcp(int x,int y){
if(x<1||x>n||y<1||y>n)return 0;
int l=0,r=n-max(x,y)+1;
while(l<r){
int mid=l+r+1>>1;
if(gh(x,x+mid-1)==gh(y,y+mid-1))l=mid;
else r=mid-1;
}
return l;
}
int lcs(int x,int y){
if(x<1||x>n||y<1||y>n)return 0;
int l=0,r=min(x,y);
while(l<r){
int mid=l+r+1>>1;
if(gh(x-mid+1,x)==gh(y-mid+1,y))l=mid;
else r=mid-1;
}
return l;
}
bool cmp(int x,int y){
int l=lcp(x,y);
return s[x+l]<s[y+l];
}
struct run{
int l,r,p;
bool operator<(const run &o)const{return l==o.l?r<o.r:l<o.l;}
bool operator==(const run &o)const{return l==o.l&&r==o.r;}
};
vector<run> runs;
void chk(int i,int j){
int l=i-lcs(i-1,j),r=j+lcp(i,j+1);
if(r-l+1>=2*(j-i+1))runs.push_back({l,r,j-i+1});
}
int stk[N],tp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>s,n=s.size(),s=' '+s+' ';
pw[0]=1;rep(i,1,n)pw[i]=pw[i-1]*131,h[i]=h[i-1]*131+s[i];
per(i,n,1){
while(tp&&cmp(i,stk[tp]))--tp;
if(tp)chk(i,stk[tp]-1);
stk[++tp]=i;
}
tp=0;
per(i,n,1){
while(tp&&!cmp(i,stk[tp]))--tp;
if(tp)chk(i,stk[tp]-1);
stk[++tp]=i;
}
sort(allc(runs)),runs.erase(unique(allc(runs)),runs.end());
cout<<runs.size()<<'\n';
for(auto i:runs)cout<<i.l<<' '<<i.r<<' '<<i.p<<'\n';
}
详细
Test #1:
score: 10
Accepted
time: 61ms
memory: 7628kb
input:
luynenolgrtkiqkdbpcoqsjyisilepmrkleqytdfmxrupcartchjwqhekspohcftpmkpfnwtmoqesqxluevqwewgylwgpdbgplwwbsqpigtayqmswjksngymtwulavrpjpomiedsmxtmpheoqogfwhtpdnaflsxwhlkrrnkfmfrcmvqelyjhfdylszqftndcynurbgwnnnrbkjfxioeptfaoervxgzzhovypdvfsiytviysqpzhkeiyibwhjviqjgpblmieugxroykgnloxpyyzzugirqbcwqdicloyulqij...
output:
7394 99 100 1 164 165 1 200 202 1 222 223 1 277 278 1 279 280 1 334 335 1 406 407 1 410 411 1 412 413 1 421 422 1 434 435 1 458 459 1 494 495 1 559 560 1 564 565 1 566 567 1 577 578 1 624 625 1 633 634 1 704 705 1 706 707 1 710 711 1 749 750 1 769 770 1 797 798 1 800 801 1 858 859 1 866 867 1 868 86...
result:
ok 7395 lines
Test #2:
score: 10
Accepted
time: 35ms
memory: 16988kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
1 1 200000 1
result:
ok 2 lines
Test #3:
score: 10
Accepted
time: 79ms
memory: 14496kb
input:
bbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaaba...
output:
102706 1 2 1 1 27 11 1 70 27 1 183 70 1 479 183 1 1254 479 1 3283 1254 1 8595 3283 1 22502 8595 1 58911 22502 1 154231 58911 3 4 1 5 7 1 7 10 2 10 13 1 12 43 16 12 113 43 12 296 113 12 775 296 12 2029 775 12 5312 2029 12 13907 5312 12 36409 13907 12 95320 36409 12 200000 95320 14 15 1 16 18 1 18 21 ...
result:
ok 102707 lines
Test #4:
score: 10
Accepted
time: 71ms
memory: 9356kb
input:
dcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcd...
output:
69092 1 28 12 1 72 28 1 188 72 1 492 188 1 1288 492 1 3372 1288 1 8828 3372 1 23112 8828 1 60508 23112 1 158412 60508 4 5 1 5 12 4 12 13 1 13 44 16 13 116 44 13 304 116 13 796 304 13 2084 796 13 5456 2084 13 14284 5456 13 37396 14284 13 97904 37396 13 200000 97904 16 17 1 17 24 4 24 25 1 25 32 4 29 ...
result:
ok 69093 lines
Test #5:
score: 10
Accepted
time: 1ms
memory: 5692kb
input:
dcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcbadcbaabcdabcddcbadcbaabcdabcddcbaabcdabcddcba
output:
31 1 28 12 1 72 28 4 5 1 5 12 4 12 13 1 13 44 16 13 100 44 16 17 1 17 24 4 24 25 1 25 32 4 29 56 12 32 33 1 33 40 4 40 41 1 41 88 16 44 45 1 45 52 4 52 53 1 53 60 4 60 61 1 61 68 4 68 69 1 69 76 4 73 100 12 76 77 1 77 84 4 84 85 1 88 89 1 89 96 4 96 97 1
result:
ok 32 lines
Test #6:
score: 10
Accepted
time: 75ms
memory: 14124kb
input:
bbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbaba...
output:
140058 1 2 1 1 34 15 1 87 34 1 227 87 1 594 227 1 1555 594 1 4071 1555 1 10658 4071 1 27903 10658 1 73051 27903 1 191250 73051 2 5 2 2 14 5 3 8 3 5 6 1 6 10 2 8 13 3 10 11 1 11 14 2 14 17 1 15 53 19 15 140 53 15 367 140 15 961 367 15 2516 961 15 6587 2516 15 17245 6587 15 45148 17245 15 118199 45148...
result:
ok 140059 lines
Test #7:
score: 10
Accepted
time: 337ms
memory: 23116kb
input:
ghbaahxvveloseywqeuokpraqgyscdcimfioohjjnwyhdyftczjorapjhncjqetfjetxnfidbgkeesajrjxkkmutayescxxndtmryuubdgijyisstqefcayeycxccwpfpdypautdbbmblfvexakzakgzpfdrdtytyzkytfdwgqarxvyuvivysbzhgcakxbfwarwvxaufsuzprxjnhenbimlqoncmojkqbgoaiifaegpvdakmhxoplzfamkodtatwghwprerxkhtqhfcofqfqrnsgxgjsgcppmlgfrxdceyuo...
output:
38316 4 5 1 8 9 1 36 37 1 39 40 1 76 77 1 84 85 1 94 95 1 102 103 1 111 112 1 124 125 1 137 138 1 158 161 2 229 230 1 273 276 2 287 288 1 342 344 1 352 353 1 412 413 1 449 450 1 458 459 1 463 464 1 514 516 1 564 565 1 588 589 1 621 622 1 630 631 1 653 654 1 678 679 1 682 683 1 689 690 1 776 779 1 78...
result:
ok 38317 lines
Test #8:
score: 10
Accepted
time: 179ms
memory: 37572kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
1 1 999998 1
result:
ok 2 lines
Test #9:
score: 10
Accepted
time: 418ms
memory: 49456kb
input:
aababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccabbccaaababbbbccaaababbbbccabbccaaababbbbccaaaba...
output:
513547 1 2 1 1 43 16 1 113 43 1 296 113 1 775 296 1 2029 775 1 5312 2029 1 13907 5312 1 36409 13907 1 95320 36409 1 249551 95320 1 653333 249551 2 5 2 5 8 1 7 16 5 9 10 1 12 13 1 12 70 27 12 183 70 12 479 183 12 1254 479 12 3283 1254 12 8595 3283 12 22502 8595 12 58911 22502 12 154231 58911 12 40378...
result:
ok 513548 lines
Test #10:
score: 10
Accepted
time: 437ms
memory: 48016kb
input:
aababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbabaababaababbbbabaababaababbbbabbbaba...
output:
700312 1 2 1 1 10 5 1 53 19 1 140 53 1 367 140 1 961 367 1 2516 961 1 6587 2516 1 17245 6587 1 45148 17245 1 118199 45148 1 309449 118199 1 810148 309449 2 6 2 4 9 3 6 7 1 7 10 2 8 17 5 10 13 1 11 19 4 15 17 1 15 87 34 15 227 87 15 594 227 15 1555 594 15 4071 1555 15 10658 4071 15 27903 10658 15 730...
result:
ok 700313 lines