QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721087 | #9406. Triangle | byron10000 | WA | 154ms | 69984kb | C++14 | 4.9kb | 2024-11-07 15:11:53 | 2024-11-07 15:11:54 |
Judging History
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define _UN using namespace
using namespace std;
const int MAXN=3e5+10;
struct SA{
char S[MAXN]; int n;
int sa[MAXN],sa1[MAXN],rk[MAXN*2],lrk[MAXN*2],cnt[MAXN],H[MAXN],st[20][MAXN];
void main(){
fill_n(lrk+1,n*2,0);
copy_n(S+1,n,rk+1);
int mxrk=*max_element(rk+1,rk+n+1);
fill_n(cnt+1,mxrk,0);
RNG(i,1,n) cnt[rk[i]]++;
RNG(i,1,mxrk) cnt[i]+=cnt[i-1];
RNG(i,1,n) sa[cnt[rk[i]]--]=i;
for(int len=1; ; len*=2){
iota(sa1+1,sa1+len+1,n-len+1);
int c=len;
RNG(i,1,n){
if(sa[i]>len) sa1[++c]=sa[i]-len;
}
assert(c==n);
fill_n(cnt+1,mxrk,0);
RNG(i,1,n) cnt[rk[i]]++;
RNG(i,1,mxrk) cnt[i]+=cnt[i-1];
IRNG(i,n,1) sa[cnt[rk[sa1[i]]]--]=sa1[i];
copy_n(rk+1,n,lrk+1);
mxrk=0;
RNG(i,1,n){
if(!(lrk[sa[i]]==lrk[sa[i-1]]&&lrk[sa[i]+len]==lrk[sa[i-1]+len])) mxrk++;
rk[sa[i]]=mxrk;
}
if(mxrk==n) break;
}
RNG(i,1,n,c=0){
if(c) c--;
if(rk[i]==1) continue;
while(S[i+c]==S[sa[rk[i]-1]+c]) c++;
H[rk[i]]=c;
}
copy_n(H+1,n,st[0]+1);
RNG(t,1,__lg(n-1)){
RNG(i,2,n-(1<<t)+1) st[t][i]=min(st[t-1][i],st[t-1][i+(1<<(t-1))]);
}
}
int lcp(int i,int j){
if(i==j) return n-i+1;
i=rk[i],j=rk[j];
if(i>j) swap(i,j);
int t=__lg(j-i);
return min(st[t][i+1],st[t][j-(1<<t)+1]);
}
} sa;
int n;
struct BIT{
int A[MAXN];
void reset(){ fill_n(A+1,n,0); }
void upd(int i,int x){
for(; i<=n; i+=i&-i) A[i]+=x;
}
int qry(int i){
int ret=0;
for(; i; i-=i&-i) ret+=A[i];
return ret;
}
} bit;
int pos[MAXN]; long ans;
struct{ string s; int c,len; } A[MAXN];
int ord[MAXN],iord[MAXN];
struct Qt{ int i; long x; }; vector<Qt> qry[MAXN];
int lcp(int i,int ip,int j,int jp){ return min({sa.lcp(pos[i]+ip,pos[j]+jp),A[i].len-ip,A[j].len-jp}); }
bool is_pre(int i,int j){ return !strncmp(A[i].s.data(),A[j].s.data(),min(A[i].len,A[j].len)); }
int cmp(int i,int j){
int p=lcp(j,0,j,A[i].len);
if(A[i].len+p<A[j].len) return A[j].s[p]-A[j].s[p+A[i].len];
p=lcp(j,0,j,A[j].len-A[i].len);
if(p==A[i].len) return 0;
return A[j].s[A[j].len-A[i].len+p]-A[i].s[p];
}
int _curcas,_ncas;
void case_main(){
cin>>n;
RNG(i,1,n) cin>>A[i].s;
sort(A+1,A+n+1,[](const auto& x,const auto& y){ return x.s<y.s; });
{
int n1=0;
RNG(i,1,n){
if(A[i].s==A[i-1].s) A[n1].c++;
else A[++n1]={A[i].s,1,int(A[i].s.size())};
}
n=n1;
}
sa.n=0;
RNG(i,1,n) pos[i]=sa.n+1,copy_n(A[i].s.data(),A[i].len,sa.S+sa.n+1),sa.n+=int(A[i].s.size());
sa.main();
iota(ord+1,ord+n+1,1);
sort(ord+1,ord+n+1,[](int i,int j){
if(!is_pre(i,j)) return i<j;
else if(i<j) return cmp(i,j)<0;
else return cmp(j,i)>0;
});
RNG(i,1,n) iord[ord[i]]=i;
ans=0;
RNG(i,1,n) qry[i].clear();
vector<int> stk;
RNG(i,1,n){
while(stk.size()&&!is_pre(stk.back(),i)) stk.pop_back();
for(int j:stk){
int l=1,r=i-1,res=i;
while(l<=r){
auto mid=(l+r)/2;
int p=lcp(mid,0,i,A[j].len);
bool flag;
if(p==A[mid].len) flag=0;
else if(p+A[j].len==A[i].len) flag=1;
else flag=A[mid].s[p]>A[i].s[A[j].len+p];
if(flag) res=mid,r=mid-1;
else l=mid+1;
}
if(res<i) qry[res-1].push_back({iord[j]-1,-1l*A[i].c*A[j].c}),qry[i-1].push_back({iord[j]-1,1l*A[i].c*A[j].c});
if(res<=j) ans+=1l*A[i].c*A[j].c*(A[j].c-1)/2;
}
stk.push_back(i);
}
RNG(i,1,n,c=0){
ans+=1l*A[i].c*(A[i].c-1)*(A[i].c-2)/6+1l*A[i].c*(A[i].c-1)/2*c;
c+=A[i].c;
}
bit.reset();
RNG(i,1,n){
bit.upd(iord[i],A[i].c);
for(auto [j,x]:qry[i]) ans+=x*bit.qry(j);
}
cout<<ans<<"\n";
}
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
// freopen("out","w",stdout);
// freopen("/dev/null","w",stderr);
#else
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int cas; cin>>cas; ::_ncas=cas;
RNG(_,1,cas) _curcas=_,case_main();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 41720kb
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: 45772kb
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: 4ms
memory: 46000kb
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: 51936kb
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: 3ms
memory: 51980kb
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: 17ms
memory: 57120kb
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: 27ms
memory: 57092kb
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: 21ms
memory: 57188kb
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: 22ms
memory: 54956kb
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: 154ms
memory: 69244kb
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: 0
Accepted
time: 148ms
memory: 69884kb
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:
ok 1003 lines
Test #12:
score: 0
Accepted
time: 126ms
memory: 69984kb
input:
1003 10 lgbpleleme u u uxpwzhga uxpwzhg u uxpwzhgaadltqqpqkbteylath u uxpwzhgaadltqqpqkbteylath uxpwzhgaadltqqpq 9 aqoxfsmqwpafbocodlpdykesadqgiggw swzjus oim aqoxfsmq aqoxfsmqwpafboc swzju nohnsjbdhljarh swzjusx aqoxf 20 mbdiqaartewavbbwbhftzwxm k mbdiqaartewavbbwbhftzwxm kx kxs kxsqv kx kx kxsqv k...
output:
70 0 290 10 604 1770 2 913 1 165 16 316 4 169 26 3 36 2 1549 2 13 15 21 14 109 34 16 1889 132 1700 1 96 17 436 2 0 6183 4144 0 4 50 4 10 5 4 4 78 10 16 97 16 50204 15871 350 3 865 46 7 0 73 38 46 29 1946 65 22088 7 91 43 310 1806 0 50 4 17 38725 262 50 0 304 141 35 50 0 22760 2973 14 410 1112 20 703...
result:
ok 1003 lines
Test #13:
score: 0
Accepted
time: 116ms
memory: 69704kb
input:
1003 7 amhy ncfsepqjimkaxkvlsqw bgk ncfsepqjim n amhyderccfrcdclbgrhxospemrlwctcnogb ncfsepqjimkaxkvlsqwzxubaz 15 ul k cqm kuixi ovrwzbvkvkzfuqtxooevyvuayhupn o kuixi ulihj k k kzlmrtwddplvqvakmeda ku k kzlmrtwddplvqvakmeda k 15 mf dwhth cwkbrvykvcvqltdovbcy dwhth dwht dwhth cwkbrvykvcvqltdovbcy dwh...
output:
4 58 203 10 8614 17 20 0 0 4 43987 18 164 144 35 412 3 19 20 51 50 0 4 16 37 1 4 14 8 526 197 71 20 26 20 35 55 16 0 3667 274 2024 4 33 19492 435 1 2 10 10 22631 32 690 1 0 13 166 561 6 67 10 33 286 4 1 89 11 18 12266 26 23 280 286 16 400 102 0 10 46 40 1 84 27 14 5699 105 197 39 818 36 6 29491 4 17...
result:
ok 1003 lines
Test #14:
score: -100
Wrong Answer
time: 132ms
memory: 69700kb
input:
1003 36 dv d dvgsku dv d d dv dv d d dv dvg dvgs dvgsku dv d d dv d d nwitakortf dv dv dvg d dvg dv d tksvgjqlfzdolvno d d dvg dv dv dvgsku dv 6 w oursusfeydeqnv wdrteonpibjzxvhzvqbytajwkgqwmucrzemrfowydhkkd wdrteonpibjzxvhzvqb wdrteo wdrteo 11 crmoyb c crmo wkyxgzsh cr flnsuvxkaqknoofhjdackgvavroh ...
output:
1840 19 9 370 7 31 892 504 6 56 150 209 41 0 255 221 1 7670 0 14 638 3 100 1365 17 3 20 16 74 20 15 496 3270 16 0 62 2 345 1 65 2277 0 1 39 0 0 1 2381 707 152 8485 289 109 2066 2803 38 197 1 46 38 44 323 14 1 10 98 2 116 38 82 0 56 2220 4 10 1879 29 241 65 17 7 10 6 8 162 20 9 2 10 4 4 0 4 76 50 194...
result:
wrong answer 894th lines differ - expected: '7', found: '8'