QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721691#9406. TrianglecaibyteWA 49ms79528kbC++143.1kb2024-11-07 16:37:362024-11-07 16:37:40

Judging History

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

  • [2024-11-07 16:37:40]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:79528kb
  • [2024-11-07 16:37:36]
  • 提交

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){
	n+=4;
	F(i,0,<4){
		a[n-i]=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(){
	cin>>cn;
	F(i,1,<=cn) cin>>s[i];
	if(cn<3){
		puts("0");return;
	}
	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);
	}
	// cerr<<a+1<<'\n';
	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(){
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	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: 15ms
memory: 79528kb

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

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
4
10
20
10
20
41
14
63
74
18
11081
0
0

result:

wrong answer 2nd lines differ - expected: '0', found: '4'