QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#720616 | #9406. Triangle | DaiRuiChen007 | WA | 186ms | 109496kb | C++17 | 3.7kb | 2024-11-07 13:28:10 | 2024-11-07 13:28:15 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=6e5+5;
struct SA {
int n,str[MAXN],sa[MAXN],rk[MAXN],wt[MAXN],len[MAXN],f[MAXN][20];
int bit(int x) { return 1<<x; }
void add(int c) { str[++n]=c; }
void build() {
iota(sa+1,sa+n+1,1);
sort(sa+1,sa+n+1,[&](int x,int y){ return str[x]<str[y]; });
for(int i=1,j;i<=n;) {
for(j=i;j<n&&str[sa[j+1]]==str[sa[i]];++j);
len[i]=j-i+1;
while(i<=j) rk[sa[i++]]=j;
}
for(int k=1;k<=n;k<<=1) {
for(int l=1,r;l<=n;++l) if(len[l]>1) {
r=l+len[l]-1;
for(int i=l;i<=r;++i) wt[sa[i]]=(sa[i]+k>n?0:rk[sa[i]+k]);
sort(sa+l,sa+r+1,[&](int x,int y){ return wt[x]<wt[y]; });
for(int i=l,j;i<=r;) {
for(j=i;j<r&&wt[sa[j+1]]==wt[sa[i]];++j);
len[i]=j-i+1;
while(i<=j) rk[sa[i++]]=j;
}
l=r;
}
}
for(int i=1,k=0;i<=n;++i) {
if(rk[i]==1) k=0;
else {
k=max(0,k-1);
while(i+k<=n&&str[i+k]==str[sa[rk[i]-1]+k]) ++k;
}
f[rk[i]][0]=k;
}
for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
f[i][k]=min(f[i][k-1],f[i+bit(k-1)][k-1]);
}
}
int lcp(int x,int y) {
int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]),k=__lg(r-l+1);
return min(f[l][k],f[r-bit(k)+1][k]);
}
} sa;
struct FenwickTree {
int tr[MAXN],s,n;
void init(int N) { n=N,fill(tr,tr+n+1,0); }
void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]+=v; }
int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
} fw;
string s[MAXN];
int n,N,cnt[MAXN],st[MAXN],ord[MAXN],rk[MAXN];
struct Trie {
int tot,tr[MAXN][26],id[MAXN];
void init() {
for(int i=0;i<=tot;++i) memset(tr[i],0,sizeof(tr[i])),id[i]=0;
tot=0;
}
int ins(const string &str) {
int p=0;
for(auto c:str) {
if(!tr[p][c-'a']) tr[p][c-'a']=++tot;
p=tr[p][c-'a'];
}
if(!id[p]) id[p]=n+1;
return id[p];
}
} tr;
struct opr { int l,r; ll c; };
vector <opr> Q[MAXN];
void solve() {
cin>>N,n=sa.n=0,tr.init();
for(int i=1;i<=N;++i) {
string str;
cin>>str;
int x=tr.ins(str);
if(x>n) {
n=x,s[x]=str,cnt[x]=1,st[x]=sa.n+1;
for(auto c:str) sa.add(c);
sa.add(str.size()-MAXN);
} else ++cnt[x];
}
sa.build();
iota(ord+1,ord+n+1,1);
sort(ord+1,ord+n+1,[&](int x,int y) {
int k=sa.lcp(st[x],st[y]),w=min(s[x].size(),s[y].size());
if(k<w) return s[x][k]<s[y][k];
if(s[x].size()<s[y].size()) {
k=sa.lcp(st[y],st[y]+w);
if(k+w<(int)s[y].size()) return s[y][k]<s[y][k+w];
w=s[y].size()-s[x].size();
k=sa.lcp(st[y]+w,st[x]);
if(k>=(int)s[x].size()) return false;
return s[y][w+k]<s[x][k];
} else {
k=sa.lcp(st[x],st[x]+w);
if(k+w<(int)s[x].size()) return s[x][k+w]<s[x][k];
w=s[x].size()-s[y].size();
k=sa.lcp(st[x]+w,st[y]);
if(k>=(int)s[y].size()) return false;
return s[y][k]<s[x][w+k];
}
});
for(int i=1;i<=n;++i) rk[ord[i]]=i,Q[i].clear();
ll ans=0;
for(int x=1;x<=n;++x) {
int p=0;
for(int i=0;i<(int)s[x].size();++i) {
p=tr.tr[p][s[x][i]-'a'];
if(!tr.id[p]) continue;
int y=tr.id[p],o=rk[y],l=sa.rk[st[x]+i+1],r=sa.rk[st[x]];
if(l>=r) continue;
if(x!=y) {
if(r-l>1) Q[o].push_back({l+1,r-1,1ll*cnt[x]*cnt[y]});
if(l<sa.rk[st[y]]&&sa.rk[st[y]]<r) ans+=1ll*cnt[y]*(cnt[y]-1)/2*cnt[x];
if(rk[x]<o&&l<r) ans+=1ll*cnt[x]*(cnt[x]-1)/2*cnt[y];
} else {
if(r-l>1) Q[o].push_back({l+1,r-1,1ll*cnt[x]*(cnt[x]-1)/2});
ans+=1ll*cnt[x]*(cnt[x]-1)*(cnt[x]-2)/6;
}
}
}
fw.init(sa.n);
for(int i=1;i<=n;++i) {
for(auto q:Q[i]) ans+=q.c*(fw.qry(q.r)-fw.qry(q.l-1));
fw.add(sa.rk[st[ord[i]]],cnt[ord[i]]);
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
int T; cin>>T;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 62156kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
16 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 63792kb
input:
14 1 lfpbavjsm 2 pdtlkfwn mbd 3 dvqksg dvqksg uhbhpyhj 4 ombwb ombwb ombwb ombwb 5 oztclz oztclz oztclz oztclz kul 6 vco vco vco dtktsqtinm vco vco 7 tb tb kowbsu ygkfphcij tb uvei tb 8 vxxtxssht abnsxbf bydaae bydaae udalyvmcef bydaae bydaae bydaae 9 aaze zvyonw qjfv mmhkef qjfv qjfv qjfv mmhkef qj...
output:
0 0 0 4 10 20 10 20 41 14 63 74 18 11081
result:
ok 14 lines
Test #3:
score: 0
Accepted
time: 3ms
memory: 61192kb
input:
11 10 bppzfsncq bppzfsncq vcqxgcehdx bppzfsncq bppzfsncq muwrcvt w aanwhqmync aanwhqmync bppzfsncq 10 t jkky t z t t z z z t 10 qidkyca uhqubvbo kosyvh gsj gsj gsj duo jrro gsj jrro 10 lhktb lhktb lhktb uohl lhktb r lhktb lhktb wruim lhktb 10 e gqvdmpvxb gqvdmpvxb gqvdmpvxb sttirbhz gqvdmpvxb zdfpm ...
output:
30 60 15 35 20 20 23 12 38 44 8047
result:
ok 11 lines
Test #4:
score: 0
Accepted
time: 3ms
memory: 65812kb
input:
11 100 kalgqjh mdszzwe qxn kalgqjh hy kalgqjh suplvp r kkeoxmx tcoise suplvp suplvp y kalgqjh vrwniyici jmnyrradyq kalgqjh kalgqjh suplvp rkg xzevyk zc suplvp hcupv kalgqjh qakyahjaoi mum pbg u ip kalgqjh kalgqjh jngc ylr suplvp qxn kalgqjh bzwodm e kalgqjh kalgqjh evmm kbymvbccs kalgqjh suplvp kalg...
output:
12478 6722 9220 6668 4934 11233 7950 5470 4525 5743 1586066
result:
ok 11 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 62524kb
input:
2 1000 t lhijhkxzzx nhfiksblww h xg z dcbmbvyz ois ynwjgfp oqzv qtoinl gr teu kmza hs t mwhewk kjmuneon bekku qheweh szhagft fcwjp bobwnap y oqpole oqzv xeaiyhfeg rjkdidea wmeslege vyyi teomn yvmcnw vnvum tgnl swqqruuvc xxllevp bov dse e b rtbhogkx nzs e bs pppyndgrrv n tzbwqdusn e xeaiyhfeg i agnet...
output:
2430570 1904282
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 31ms
memory: 67880kb
input:
503 16 yh yh yhc yhc yhcowdfqlwfidnx yhc yhc yh yhcowdfqlwfidn yhcowdfqlwfidnx yh h yh yhcowdfqlwfidnx yhcowdfqlwfidnx yhc 19 nb nbg vpfkllgv nmzqfsuafqtayjjjcidpygz nb nb gutq n omyuvm fgxtfbhuglxyiumi nbghjuti nbg nb fgxt nbghjuti n nb nbg n 7 rtjiwfidoahckhvgoxvvrncqvgerqiuaruiftakvugsgnsw wllcan...
output:
531 485 6 12 4 118 6 3 1635 18 373 20 954 6208 45 12 1124 79 267 2 5778 22 13 1 1 16 630 0 7 16315 0 2155 2308 26 936 109 103 5 0 2492 7 2 114 144 11 158 0 0 101 455 0 12234 78 631 5402 94 66 84 161 4412 5 3 81 22 20 13 52 632 6 137 56 2 3 64521 122 330 0 0 7 0 113 249 8 301 335 1825 110 4 108 50 10...
result:
ok 503 lines
Test #7:
score: 0
Accepted
time: 26ms
memory: 69964kb
input:
503 23 rjyyivdg n n n n n n n nmr n nmrk nm rjyyivdguyiffnvunoxconw n n n o lixclcmwthwkrsi mqluhyypgfkmdvgpzju n nmrk rjy n 15 jotwxwhaqdxmazhslyouztprzlirisvwvduojb jot jotwxw j jotwx jotwx gohg j gdgneodagmdhvvapjh jotwxw xs vurk vurk j xs 7 xrczucnkbemaymvabkkwnn xrczucnkbemaymvabkkwnn xrczucnkb...
output:
855 58 35 0 1 56 2 112 1 8465 242 56 110 23 544 0 3 17 29 11 764 20 9 0 4 77 812 35 4 10 32 437 9 2364 3 2 11 2 421 50 4 107 1 62 1120 3 1 16 3970 1147 1026 8 4 85 9 31 61 16 205 2 2 84 238 1 1 51 4 0 16 61 331 4 16 7 0 7 148 10 13 2 1 37 1 67 0 296 1 0 644 32 2 10 0 5 126 3490 4 0 10 331 1216 7921 ...
result:
ok 503 lines
Test #8:
score: 0
Accepted
time: 33ms
memory: 69952kb
input:
503 5 ljtolmgjndlwoyjjttak mihjdhkyfnafwrpeuiuiurusvsnu ljtolmgjndlwoyjjttak mihjd ljtolmgjndlwoyjjttak 25 lhx lh lhx lh k lh kninp l lhx lhx izeqohkpfuovopebttqaufmmlivd lhx lhx qid lhx lh lhx lhx oklb l lhx lhx lhx lhx l 9 mxeonfwpujrilfigjoiyjkzdmi fezhyrcyqy mx fezh f dmvfbklnkxmnetib dmvfbkln m...
output:
4 1476 27 26 117970 2 105 30 4 737 4 2 19 48 34 434 6 78331 22 23 0 228 56 4 3 305 9 84 132 199 20 3 4057 0 0 20 35 34 48 4 266 14 17 4788 545 28989 0 10 535 84 1 1775 322 11 57 16 15 1331 5 0 10 5 183 8 2 237 10 0 60 20 42 7 10 297 14 210 6254 7 3 0 13 2744 119 47 0 1 68114 17 1 2 1 7 1 2 113 26 0 ...
result:
ok 503 lines
Test #9:
score: 0
Accepted
time: 28ms
memory: 69920kb
input:
503 11 wkeoqqqpvmgdv w w w wkeoqqqpvmgdv sgrwmsfwclpamgq wkeoqqqpvm qkmbyvcxjsh wkeoqqqpvm wke wkeoqqqpvmgdv 7 otd qelodfwrqeprgyvzbcjljx qe qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj qelodfwrqeprgyvzbcjlj c 15 rce rce fwq fwqqfcjrhqot rceft jkdrcehfwhqkupe fwq r jkdr fwq rceft rce fwqqfcjrhqot fwq...
output:
156 17 213 12 20 1 374 4 0 26 26 3 122 30 4005 24 1385 50 84 44 0 112 42 36 19 887 99 5 9 13 2 5029 52 14 84 116 2 10 4 8 141 9287 822 37 5 13 25 1030 0 2 3 35 81 1 0 1 138 0 578 7 30 636 63 22 2118 863 5377 33 34 10 156 336 1 7 7 4 1793 2 124 13 4 2015 7 23 1 4516 3 17 6 35 13336 9 61 3093 0 1 7 22...
result:
ok 503 lines
Test #10:
score: 0
Accepted
time: 152ms
memory: 106844kb
input:
1003 3 mpfowyd mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi 3 nyfcq nyfcqgrmshiwmgcbukozvetdggebkkychamof nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi 8 yoeqyfcjsywowdrlzzybjvtycqvizzomc zci yoeqyfc zcinc yoeqyfcjsywowdrlzzybjvtycqvizzomc y zcinc ...
output:
0 1 26 10 66 403 1 265 1025 16 329 4 1219 1 10 70 30 182 60 5 71 1 20 5343 22328 40667 90 6983 66 10 35 20 250 307 913 98 44 5393 56 280 270 3 3 2229 77 17 774 50 5 21 0 208 8 14 185 35 20 11 465 132 176 10 0 10 1704 13 44 141 0 0 5 10 79 17 213 10 108 0 0 289 10 255 27 493 4 1 24 379 30 9 284 173 2...
result:
ok 1003 lines
Test #11:
score: -100
Wrong Answer
time: 186ms
memory: 109496kb
input:
1003 6 exssl exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx f exss exs exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx 7 hzzev hzzevmltbehnvjfhsz hzzevmltbe hzzevmltbehnvjfhszqzobn hzzevmltbehnvjf hm hzzevmltbehnvjfhszqzobn 9 rdx rdxnxdfcyrdpgwzwtqgtu rdx rdxnxdfcyrdpgwzwtqgtu f kpotnxntufvd kpotnxntufvdlmij...
output:
3 19 41 134 107 2 372 0 466 456 20 13 25 339 64 170 1 5 27295 3 1 221 116 11 29 19 1006 16827 16 19863 4 6 5784 3 20 21130 66 1275 100 731 83 3 84 0 32 3 615 207 8 44 245 48 165 18050 128 11 864 21 3 1221 120 51 21 8 247 302 0 1098 0 57 42 20 0 845 1 84 16 4 0 2 836 482 4 12 150 654 1035 142 291 34 ...
result:
wrong answer 642nd lines differ - expected: '30044', found: '30035'