QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729985 | #9406. Triangle | Wuyanru | WA | 96ms | 89616kb | C++14 | 5.6kb | 2024-11-09 18:12:14 | 2024-11-09 18:12:15 |
Judging History
answer
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
using pl=pair<ll,ll>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod1=998244853,mod2=1000000009;
const int base=1145141;
struct node{ int a,b,c;}v[300001],vv[300001];
int son[300005][26];
int num[300005];//这个节点对应多少字符串
int sa[600005],rk[1200005];
int num1[600005],num2[600005];
int tmp[600005],cnt[600005];
ll p1[600005],p2[600005];
ll h1[600005],h2[600005];
ll ff[600005],cc[600005];
int ed[300005],id[300005];
int hi[600005],st[21][600005];
char t[600005];
char s[300005];
int c,tot,n,rt;
ll ans;
inline void clear()
{
c=tot=rt=0;
}
inline int ins(int &p,char *s)
{
if(!p) p=++tot,num[p]=0,memset(son[p],0,sizeof(son[p]));
if(!s[0]){ num[p]++;return p;}
t[++c]=s[0];return ins(son[p][s[0]-'a'],s+1);
}
inline void SA()
{
int lim=max(27,c);
for(int i=1;i<=c;i++) rk[i]=t[i]=='$'?1:t[i]-'a'+2;
for(int i=c+1;i<=2*c;i++) rk[i]=0;
for(int P=0;(1<<P)<=c;P++)
{
memset(cnt,0,sizeof(int)*(lim+2));
for(int i=1;i<=c;i++) num1[i]=rk[i],num2[i]=rk[i+(1<<P)],cnt[num2[i]+1]++;
for(int i=1;i<=lim;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=c;i++) tmp[++cnt[num2[i]]]=i;
memset(cnt,0,sizeof(int)*(lim+2));
for(int i=1;i<=c;i++) cnt[num1[i]+1]++;
for(int i=1;i<=lim;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=c;i++) sa[++cnt[num1[tmp[i]]]]=tmp[i];
for(int i=1;i<=c;i++)
{
int p=sa[i-1],q=sa[i];
if(num1[p]==num1[q]&&num2[p]==num2[q]) rk[q]=rk[p];
else rk[q]=rk[p]+1;
}
}
// printf("%s c=%d\n",t+1,c);
// for(int i=1;i<=c;i++) printf("%2d%c",sa[i]," \n"[i==c]);
// for(int i=1;i<=c;i++) printf("%2d%c",rk[i]," \n"[i==c]);
for(int i=1,j=0;i<=c;i++)
{
if(j) j--;
int p=sa[rk[i]-1];
while(t[i+j]==t[p+j]) j++;
hi[rk[i]]=j;
// printf("%d and %d : %d\n",i,p,j);
}
// for(int i=1;i<=c;i++) printf("%2d%c",hi[i]," \n"[i==c]);
for(int i=1;i<=c;i++) st[0][i]=hi[i];
for(int j=1;(1<<j)<=c;j++) for(int i=1;i+(1<<j)-1<=c;i++) st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
inline int get(int w1,int w2)
{
if(w1==w2) return c-w1+1;
w1=rk[w1],w2=rk[w2];if(w1>w2) swap(w1,w2);
int num=31-__builtin_clz(w2-w1);
return min(st[num][w1+1],st[num][w2-(1<<num)+1]);
}
inline bool check(int l1,int r1,int l2,int r2)
{
//是否有 t[l1,r1] > t[l2,r2]
int lcp=min(get(l1,l2),min(r1-l1+1,r2-l2+1));
// printf("check %d %d %d %d lcp=%d\n",l1,r1,l2,r2,lcp);
if(l1+lcp<=r1&&l2+lcp<=r2) return t[l1+lcp]>t[l2+lcp];
return l1+lcp<=r1;
}
int tt[600001];
inline int lowbit(int i){ return i&(-i);}
inline void add(int x,int y){ while(x<=c) tt[x]+=y,x+=lowbit(x);}
inline int get(int x){ int ans=0;while(x) ans+=tt[x],x-=lowbit(x);;return ans;}
inline void solve()
{
n=read();
for(int i=1;i<=n;i++)
{
scanf("%s",s+1);t[++c]='$';
id[i]=ins(rt,s+1),ed[i]=c;
}
t[c+1]=0;SA();
p1[0]=p2[0]=1;
for(int i=1;i<=c;i++) p1[i]=p1[i-1]*base%mod1,p2[i]=p2[i-1]*base%mod2;
int len=-1;ll now1=0,now2=0;
for(int i=c;i;i--)
{
if(t[i]=='$') len=-1,now1=now2=h1[i]=h2[i]=0;
else
{
len++;
h1[i]=now1=(now1+p1[len]*(t[i]-'a'+1))%mod1;
h2[i]=now2=(now2+p2[len]*(t[i]-'a'+1))%mod2;
}
}
map<pl,int>vis;int P=0;
for(int i=1;i<=c;i++)
{
int p=sa[i];ff[p]=cc[p]=0;
if(t[p]=='$') continue;
if(t[p-1]=='$') P++,vis[pl(h1[p],h2[p])]++;
ff[p]=P-vis[pl(h1[p],h2[p])];
}
for(int i=1;i<=c;i++)
{
int p=sa[i];
if(t[p]!='$') cc[p]=vis[pl(h1[p],h2[p])];
}
// for(int i=1;i<=c;i++) printf("%lld%c",ff[i]," \n"[i==c]);
// for(int i=1;i<=c;i++) printf("%lld%c",cc[i]," \n"[i==c]);
ans=0;ll v1=0,v2=0;
for(int i=1;i<=n;i++)//枚举x
{
int now=rt,st=ed[i-1]+2,ed=::ed[i];
vc<pi>V;
for(int j=st;j<ed;j++)
{
now=son[now][t[j]-'a'];
ans+=(ll)num[now]*max(0ll,ff[st]-ff[j+1]-cc[j+1]);
// printf("st=%d ed=%d j=%d : %d %lld\n",st,ed,j,num[now],max(0ll,ff[st]-ff[j+1]-cc[j+1]));
if(num[now]&&check(st,j,j+1,ed))
{
// printf("%d ~ %d : %d\n",st,j,num[now]);
ans-=(ll)num[now]*(num[now]+1)/2;
}
V.push_back(pi(st,j));
V.push_back(pi(j+1,ed));
v[j-st+1].c=num[now];
}
int f=ff[st],c=cc[st],all=ed-st;
v1+=(ll)(c-1)*(c-2)/2;
v2+=(ll)(c-1)*f;
sort(V.begin(),V.end(),[](pi a,pi b)
{
return check(b.first,b.second,a.first,a.second);
});
int rk=0;
for(unsigned i=0;i<V.size();i++)
{
if(!i||check(V[i].first,V[i].second,V[i-1].first,V[i-1].second)) rk++;
if(V[i].first==st) v[V[i].second-st+1].a=rk;
else v[V[i].first-st].b=rk;
}
memcpy(vv,v,sizeof(node)*(all+1));
sort(v+1,v+all+1,[](node a,node b){ return a.a<b.a;});
sort(vv+1,vv+all+1,[](node a,node b){ return a.b<b.b;});
ll val=0,sum=0;now=1;
for(int j=1;j<=all;j++)
{
while(now<=all&&vv[now].b<v[j].a) add(vv[now].a,vv[now].c),sum+=vv[now].c,now++;
val+=v[j].c*(sum-get(v[j].b));
}
while(now>1) now--,add(vv[now].a,-vv[now].c);
for(int i=1;i<=all;i++) if(v[i].a>v[i].b) val-=(ll)v[i].c*v[i].c;
ans-=val/2;// printf("val=%lld\n",val);
}
ans+=v1/3+v2/2;
// printf("%lld %lld\n",v1,v2);
printf("%lld\n",ans);
}
int main()
{
int T=read();
while(T--) clear(),solve();
return 0;
}
/*
1
3
aaa
aaa
aaaa
ans=1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 52968kb
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: 63284kb
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: 0ms
memory: 61204kb
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: 8ms
memory: 69492kb
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: 4ms
memory: 65416kb
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: -100
Wrong Answer
time: 96ms
memory: 89616kb
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:
wrong answer 161st lines differ - expected: '4', found: '3'