QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719893 | #9406. Triangle | byron10000 | WA | 3ms | 47820kb | C++14 | 4.9kb | 2024-11-07 09:39:54 | 2024-11-07 09:39:55 |
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];
}
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 _curcas;
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;
RNG(_,1,cas) _curcas=_,case_main();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 41656kb
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: 3ms
memory: 47820kb
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 11082
result:
wrong answer 14th lines differ - expected: '11081', found: '11082'