QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#716406#9406. TriangledaduoliWA 22ms74816kbC++144.2kb2024-11-06 15:10:342024-11-06 15:10:34

Judging History

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

  • [2024-11-06 15:10:34]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:74816kb
  • [2024-11-06 15:10:34]
  • 提交

answer

#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=6e5+10;
int n,cnt;
char ch[MAXN];
int m,sa[MAXN],x[MAXN],y[MAXN],c[MAXN],st[20][MAXN],logg[MAXN];
int tlen[MAXN];
bool pd[MAXN]; 
void tsort(int *sa,int *x,int *y) {
	for(int i=1;i<=m;++i) c[i]=0;
	for(int i=1;i<=cnt;++i) ++c[x[i]];
	for(int i=1;i<=m;++i) c[i]+=c[i-1];
	for(int i=cnt;i;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
}
void SA() { m=130;
	for(int i=1;i<=cnt;++i) x[i]=ch[i],y[i]=i;
	tsort(sa,x,y);
	for(int k=1;k<=cnt;k<<=1) {
		int num=0;
		for(int i=cnt-k+1;i<=cnt;++i) y[++num]=i;
		for(int i=1;i<=cnt;++i) if(sa[i]>k) y[++num]=sa[i]-k;
		tsort(sa,x,y); swap(x,y);
		x[sa[1]]=num=1;
		for(int i=2;i<=cnt;++i) {
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
		}
		if(num==cnt) break;
		m=num;
	}
}
int h[MAXN],rk[MAXN];
void get_height() {
	int k=0;
	for(int i=1;i<=cnt;++i) rk[sa[i]]=i;
	for(int i=1;i<=cnt;++i) {
		if(rk[i]==1) continue;
		if(k) --k;
		int j=sa[rk[i]-1];
		while(i+k<=cnt&&j+k<=cnt&&ch[i+k]==ch[j+k]) ++k;
		h[rk[i]]=k;
	}
}
void init() {
	for(int i=2;i<=cnt;++i) logg[i]=logg[i/2]+1;
	for(int i=1;i<=cnt;++i) st[0][i]=h[i];
	for(int i=1;i<=logg[cnt];++i) {
		int R=cnt-(1<<i)+1;
		for(int j=1;j<=R;++j) 
			st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	}
}
int query(int l,int r) {
	int k=logg[r-l+1];
	return min(st[k][l],st[k][r-(1<<k)+1]);
}
int sum[MAXN],R[MAXN];
int op,TT;
struct tree_array {
	LL tr[MAXN];
	int lb(int x) {
		return x&(-x);
	}
	void update(int x,int val) {
		for(int i=x;i<=cnt;i+=lb(i)) tr[i]+=val;
	}
	LL query(int x) { LL res=0;
		for(int i=x;i;i-=lb(i)) res+=tr[i];
		return res;
	}
}T,T1;
int top;
struct pt {
	int len,sz,l,r;
	vector<int> e;
}ind[MAXN];
struct ddl {
	int lim,x,y;
	friend bool operator <(ddl a,ddl b) {
		return a.lim>b.lim;
	}
};
void vmain() {
	scanf("%d",&n);
	++op;
//	if(op==286) {
//		cout<<n<<" ";
//	}
	for(int i=1;i<=n;++i) { string st; cin>>st; int len=st.size();
		int sta=cnt+1; pd[sta]=1;
		tlen[sta]=len;
		for(int j=0;j<len;++j) ch[++cnt]=st[j];
		ch[++cnt]='A';
//		if(op==286) {
//			cout<<st<<endl;
//		}
	} SA(); get_height(); init(); LL ans=0;
//	for(int i=1;i<=cnt;++i) {
//		cout<<sa[i]<<" ";
//	}
	for(int i=1;i<=cnt;++i) sum[i]=sum[i-1]+pd[sa[i]];
	int lt=0;
	for(int i=cnt;i>=1;--i) {
		if(pd[sa[i]]) {
			R[i]=i+1;
			if(lt&&query(i+1,lt)>=tlen[sa[i]]&&tlen[sa[i]]==tlen[sa[lt]]) R[i]=R[lt];
			lt=i;
		} else {
			R[i]=i;
			if(lt&&query(i+1,lt)>tlen[sa[lt]]) R[i]=R[lt];
		}
	}
//	for(int i=1;i<=cnt;++i) {
//		cout<<i<<":"<<R[i]<<endl;
//	}
	top=0;
	for(int i=1;i<=cnt;++i) {
		if(!pd[sa[i]]) continue;
		while(top) {
			int t=ind[top].e[0];
			if(query(t+1,i)<ind[top].len) {
				for(auto t:ind[top].e) T.update(t,-1);
				--top;
			} else break;
		}
		for(int j=1;j<=top;++j) {
			int t=rk[sa[i]+ind[j].len]; t=R[t];
//			if(i==9) {
//				cout<<t<<" ";
//			}
			if(t<=i-1) ans+=(LL)ind[j].sz*(sum[i-1]-sum[t]);
			if(t<ind[j].e[0]) {
				ans-=(LL)ind[j].sz*ind[j].sz;
				ans+=(LL)ind[j].sz*(ind[j].sz-1)/2;
			}
		} priority_queue<ddl> q; vector<pi> vv;
//		cout<<i<<" "<<ans<<endl;
		for(int j=1;j<=top;++j) {
			int t=rk[sa[i]+ind[j].len]; t=R[t];
			while(!q.empty()) { ddl u=q.top();
				if(u.lim>ind[j].e[0]) break;
				q.pop(); T1.update(u.x,u.y); vv.pb(u.x,u.y);
			}
			ans-=(LL)(T1.query(cnt)-T1.query(t))*ind[j].sz;
			q.push((ddl){t,ind[j].e[0],ind[j].sz});
		}
//		cout<<i<<" "<<ans<<endl;
		for(auto t:vv) T1.update(t.fi,-t.se);
		if(tlen[sa[i]]!=ind[top].len) {
			ind[++top].e.clear(); ind[top].e.pb(i);
			ind[top].l=ind[top].r=i; ind[top].len=tlen[sa[i]]; ind[top].sz=1;
		} else {
			ind[top].e.pb(i); ind[top].r=i; ++ind[top].sz;
		}
//		cout<<i<<" "<<ans<<endl;
	}
//	if(TT<500)
	printf("%lld\n",ans);
	for(int i=1;i<=cnt+1;++i) {
		pd[i]=0; tlen[i]=h[i]=rk[i]=sa[i]=x[i]=y[i]=c[i]=0;
		sum[i]=0;
	} cnt=0;
}
int main () {
	int T=1; scanf("%d",&T); TT=T; while(T--) vmain();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 59840kb

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: 22ms
memory: 67576kb

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: 18ms
memory: 69792kb

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: -100
Wrong Answer
time: 12ms
memory: 74816kb

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
1586061

result:

wrong answer 11th lines differ - expected: '1586066', found: '1586061'