QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#729900#9406. TriangleWuyanruWA 95ms93684kbC++145.3kb2024-11-09 17:59:452024-11-09 17:59:45

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 17:59:45]
  • 评测
  • 测评结果:WA
  • 用时:95ms
  • 内存:93684kb
  • [2024-11-09 17:59:45]
  • 提交

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;(2<<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,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;
	}

	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));
	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]);
			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;
	}
	ans+=v1/3+v2/2;
	printf("%lld\n",ans);
}
int main()
{
	int T=read();
	while(T--) clear(),solve();
	return 0;
}
/*
1
5
xxx
xxx
xxxx
xxxxx
xxxxx
ans=10
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 53188kb

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: 0ms
memory: 61140kb

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: 61108kb

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: 0ms
memory: 71532kb

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: 65428kb

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: 95ms
memory: 93684kb

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'