QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722250#9406. TrianglecaibyteWA 788ms139004kbC++143.2kb2024-11-07 18:19:182024-11-07 18:19:19

Judging History

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

  • [2024-11-07 18:19:19]
  • 评测
  • 测评结果:WA
  • 用时:788ms
  • 内存:139004kb
  • [2024-11-07 18:19:18]
  • 提交

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=3e6+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;
	}
}
int x[N],y[N],c[N];
void SA(){
	int m=127;
	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<<1)){
		sa[i]=rk[i]=h[i]=p[i]=rev[i]=a[i]=0;
	}
	T.init();
	F(i,1,<=siz) st[i]=cnt[i]=0;
	n=siz=0;
}
bool cmp(const string&x,const string&y){
	return x.size()<y.size();
};
ll ss;
inline void solve(){
	if(clock()*1.0/CLOCKS_PER_SEC>=0.8){
		cout<<ss<<"!!!\n";
		exit(0);
	}
	cin>>cn;
	F(i,1,<=cn) cin>>s[i];
	sort(s+1,s+cn+1,cmp);
	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();
	ss+=n;
	ll ans=0;
	F(i,2,<=n){// C
		while(siz&&s[st[siz]].size()>h[i]) --siz;
		if(!rev[sa[i]]) continue;
		ss-=siz;
		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);
	}
	assert(ss>=0);
	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: 23ms
memory: 136952kb

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: 115ms
memory: 137016kb

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: 104ms
memory: 136780kb

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: 118ms
memory: 136816kb

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: 27ms
memory: 139004kb

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: 788ms
memory: 136820kb

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
12...

result:

wrong answer 91st lines differ - expected: '106', found: '12201!!!'