QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719913 | #9406. Triangle | byron10000 | WA | 4ms | 46036kb | C++14 | 5.0kb | 2024-11-07 09:48:22 | 2024-11-07 09:48:23 |
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(){
iota(sa+1,sa+n+1,1);
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);
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;
if(_curcas==14){
RNG(i,1,n) cout<<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);
}
if(_ncas<=3)
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: 39672kb
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: -100
Wrong Answer
time: 4ms
memory: 46036kb
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:
o cyt cyt rfhgomg cyt cyt k cyt kwvd cteyfpl yiglr cteyfpl sryq vgxod cyt vjzuvwsj o cyt cteyfpl cyt rc cyt cyt zaczhqq bghogpzh bppygqqyqf unx sdhfsay sdhfsay cteyfpl cteyfpl cteyfpl onvw kwvd hfxucu cteyfpl uhivp cyt zaczhqq tvifsf cyt cteyfpl fdiajuuc cyt hvcph cyt bftskm mgpooqys ytz sojcnzuxq s...
result:
wrong answer 1st lines differ - expected: '0', found: 'o cyt cyt rfhgomg cyt cyt k cy...jcnzuxq ncitwxsdpp sojcnzuxq o '