QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721529#9406. TrianglecaibyteWA 52ms79420kbC++143.0kb2024-11-07 16:19:162024-11-07 16:19:16

Judging History

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

  • [2024-11-07 16:19:16]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:79420kb
  • [2024-11-07 16:19:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F(i,l,r) for(int i=l;i r;++i)
#define R(i,r,l) for(int i=r;i l;--i)
#define pb push_back
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
template<class T=int>inline T read(){
	T x=0;bool b=0;char c=getchar();
	while(!isdigit(c)) b|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return b?-x:x;
}
inline char readc(){
	char c=getchar();
	while(isspace(c)) c=getchar();
	return c;
}
namespace{
//
const int N=1.5e6+3;
int cn,n,sa[N],rk[N],h[N],p[N],rev[N];
char a[N];
string s[N];
inline void ins(int x){
	F(i,0,<4){
		a[++n]=x%26+'A';
		x/=26;
	}
}
void SA(){
	int m=127;
	static int x[N],y[N],c[N];
	F(i,0,<=m) c[i]=0;
	F(i,1,<=n) ++c[x[i]=a[i]];
	F(i,1,<=m) c[i]+=c[i-1];
	R(i,n,>=1) sa[c[x[i]]--]=i;
	for(int k=1;k<n;k<<=1){
		int cnt=0;
		F(i,n-k+1,<=n) y[++cnt]=i;
		F(i,1,<=n) if(sa[i]>k) y[++cnt]=sa[i]-k;
		F(i,0,<=m) c[i]=0;
		F(i,1,<=n) ++c[x[i]];
		F(i,1,<=m) c[i]+=c[i-1];
		R(i,n,>=1) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		swap(x,y);
		x[sa[1]]=m=1;
		F(i,2,<=n){
			if(y[sa[i-1]]!=y[sa[i]]||y[sa[i-1]+k]!=y[sa[i]+k]) ++m;
			x[sa[i]]=m;
		}
		if(m==n) break;
	}
	F(i,1,<=n) rk[sa[i]]=i;
	int p=0;
	F(i,1,<=n){
		if(rk[i]==1) continue;
		if(p) --p;
		while(a[i+p]==a[sa[rk[i]-1]+p]) ++p;
		h[rk[i]]=p;
	}
}
struct bit{
	ll c[N];
	void init(){
		F(i,0,<=n) c[i]=0;
	}
	void write(int x,ll k){
		for(;x;x&=x-1) c[x]+=k;
	}
	ll query(int x){
		ll res=0;
		for(;x<=n;x+=x&-x) res+=c[x];
		return res;
	}
} T;
typedef pair<int,int> pii;
int st[N],siz;
ll cnt[N];
priority_queue<pii,vector<pii>,greater<pii>> q;
inline void reset(){
	F(i,1,<=n){
		sa[i]=rk[i]=h[i]=p[i]=rev[i]=a[i]=cnt[i]=0;
	}
	T.init();
	F(i,1,<=siz) st[i]=0;
	n=siz=0;
}
inline void solve(){
	cn=read();
	F(i,1,<=cn) cin>>s[i];
	sort(s+1,s+cn+1,[](const string&x,const string&y){
		return x.size()<y.size();
	});
	F(i,1,<=cn){
		p[i]=n+1;rev[n+1]=i;
		for(char c:s[i]){
			a[++n]=c;
		}
		ins(i);
	}
	SA();
	ll ans=0;
	F(i,2,<=n){// C
		while(siz&&s[st[siz]].size()>h[i]) --siz;
		if(!rev[sa[i]]) continue;
		F(j,1,<=siz){// A
			while(!q.empty()&&q.top().first<rk[p[st[j]]]){
				int x=q.top().second;q.pop();
				T.write(rk[p[st[x]]],-cnt[x]);
			}
			int x=rk[sa[i]+s[st[j]].size()];
			ans+=T.query(x)*cnt[j];
			if(x<rk[p[st[j]]]) ans-=cnt[j]*(cnt[j]+1)/2,T.write(rk[p[st[j]]],-cnt[j]);
			else if(x<i) q.push({x,j});
		}
		while(!q.empty()){
			int x=q.top().second;q.pop();
			T.write(rk[p[st[x]]],-cnt[x]);
		}
		F(j,1,<=siz){
			int x=rk[sa[i]+s[st[j]].size()];
			if(x<i) T.write(rk[p[st[j]]],cnt[j]);
		}
		if(siz&&s[st[siz]].size()==s[rev[sa[i]]].size()) ++cnt[siz];
		else ++siz,cnt[siz]=1,st[siz]=rev[sa[i]];
		T.write(i,1);
	}
	cout<<ans<<'\n';
	reset();
}
void work(){
	int T=read();
	while(T--) solve();
}
}
#if 0
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#else
#define file(x)
#endif
signed main(){file("");work();return 0;}

詳細信息

Test #1:

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

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: 52ms
memory: 77428kb

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: 48ms
memory: 79420kb

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: 49ms
memory: 79384kb

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
1586264

result:

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