QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720349#9406. TriangleDaiRuiChen007WA 24ms65720kbC++173.4kb2024-11-07 12:03:482024-11-07 12:03:49

Judging History

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

  • [2024-11-07 12:03:49]
  • 评测
  • 测评结果:WA
  • 用时:24ms
  • 内存:65720kb
  • [2024-11-07 12:03:48]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=6e5+5;
struct SA {
	int n,str[MAXN],sa[MAXN],rk[MAXN],wt[MAXN],len[MAXN],f[MAXN][20];
	int bit(int x) { return 1<<x; }
	void add(int c) { str[++n]=c; }
	void build() {
		iota(sa+1,sa+n+1,1);
		sort(sa+1,sa+n+1,[&](int x,int y){ return str[x]<str[y]; });
		for(int i=1,j;i<=n;) {
			for(j=i;j<n&&str[sa[j+1]]==str[sa[i]];++j);
			len[i]=j-i+1;
			while(i<=j) rk[sa[i++]]=j;
		}
		for(int k=1;k<=n;k<<=1) {
			for(int l=1,r;l<=n;++l) if(len[l]>1) {
				r=l+len[l]-1;
				for(int i=l;i<=r;++i) wt[sa[i]]=(sa[i]+k>n?0:rk[sa[i]+k]);
				sort(sa+l,sa+r+1,[&](int x,int y){ return wt[x]<wt[y]; });
				for(int i=l,j;i<=r;) {
					for(j=i;j<r&&wt[sa[j+1]]==wt[sa[i]];++j);
					len[i]=j-i+1;
					while(i<=j) rk[sa[i++]]=j;
				}
				l=r;
			}
		}
		for(int i=1,k=0;i<=n;++i) {
			k=max(0,k-1);
			while(str[i+k]==str[sa[rk[i]-1]+k]) ++k;
			f[rk[i]][0]=k;
		}
		for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
			f[i][k]=min(f[i][k-1],f[i+bit(k-1)][k-1]);
		}
	}
	int lcp(int x,int y) {
		int l=min(rk[x],rk[y])+1,r=max(rk[x],rk[y]),k=__lg(r-l+1);
		return min(f[l][k],f[r-bit(k)+1][k]);
	}
}	sa;
struct FenwickTree {
	int tr[MAXN],s,n;
	void init(int N) { n=N,fill(tr,tr+n+1,0); }
	void add(int x,int v) { for(;x<=n;x+=x&-x) tr[x]+=v; }
	int qry(int x) { for(s=0;x;x&=x-1) s+=tr[x]; return s; }
}	fw;
string s[MAXN];
int n,N,cnt[MAXN],st[MAXN],ord[MAXN],rk[MAXN];
struct Trie {
	int tot,tr[MAXN][26],id[MAXN];
	void init() {
		for(int i=0;i<=tot;++i) memset(tr[i],0,sizeof(tr[i])),id[i]=0;
		tot=0;
	}
	int ins(const string &str) {
		int p=0;
		for(auto c:str) {
			if(!tr[p][c-'a']) tr[p][c-'a']=++tot;
			p=tr[p][c-'a'];
		}
		if(!id[p]) id[p]=n+1;
		return id[p];
	}
}	tr;
struct opr { int l,r; ll c; };
vector <opr> Q[MAXN];
void solve() {
	cin>>N,n=sa.n=0,tr.init();
	for(int i=1;i<=N;++i) {
		string str;
		cin>>str;
		int x=tr.ins(str);
		if(x>n) {
			n=x,s[x]=str,cnt[x]=1,st[x]=sa.n+1;
			for(auto c:str) sa.add(c);
			sa.add(-MAXN+str.size());
		} else ++cnt[x];
	}
	sa.build();
	iota(ord+1,ord+n+1,1);
	sort(ord+1,ord+n+1,[&](int x,int y){
		int k=sa.lcp(st[x],st[y]),w=min(s[x].size(),s[y].size());
		if(k<w) return s[x][k]<s[y][k];
		if(s[x].size()<s[y].size()) {
			k=sa.lcp(st[y],st[y]+w);
			if(k+w>(int)s[y].size()) return false;
			return s[y][k]<s[y][k+w];
		} else {
			k=sa.lcp(st[x],st[x]+w);
			if(k+w>(int)s[x].size()) return false;
			return s[x][k+w]<s[x][k];
		}
	});
	for(int i=1;i<=n;++i) rk[ord[i]]=i,Q[i].clear();
	ll ans=0;
	for(int x=1;x<=n;++x) {
		int p=0;
		for(int i=0;i<(int)s[x].size();++i) {
			p=tr.tr[p][s[x][i]-'a'];
			if(!tr.id[p]) continue;
			int y=tr.id[p],o=rk[y],l=sa.rk[st[x]+i+1],r=sa.rk[st[x]];
			if(l>=r) continue;
			if(x!=y) {
				if(r-l>1) Q[o].push_back({l+1,r-1,1ll*cnt[x]*cnt[y]});
				if(l<sa.rk[st[y]]&&sa.rk[st[y]]<r) ans+=1ll*cnt[y]*(cnt[y]-1)/2*cnt[x];
				if(rk[x]<o&&l<r) ans+=1ll*cnt[x]*(cnt[x]-1)/2*cnt[y];
			} else {
				if(r-l>1) Q[o].push_back({l+1,r-1,1ll*cnt[x]*(cnt[x]-1)/2});
				ans+=1ll*cnt[x]*(cnt[x]-1)*(cnt[x]-2)/6;
			}
		}
	}
	fw.init(sa.n);
	for(int i=1;i<=n;++i) {
		for(auto q:Q[i]) ans+=q.c*(fw.qry(q.r)-fw.qry(q.l-1));
		fw.add(sa.rk[st[ord[i]]],cnt[ord[i]]);
	}
	cout<<ans<<"\n";
}
signed main() {
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 62144kb

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

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: 11ms
memory: 61740kb

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: 5ms
memory: 61984kb

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

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: 24ms
memory: 65720kb

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 502nd lines differ - expected: '69739438680', found: '69739438235'