QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719858#9406. TrianglekonyakestRE 155ms99144kbC++175.0kb2024-11-07 09:25:502024-11-07 09:25:52

Judging History

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

  • [2024-11-07 09:25:52]
  • 评测
  • 测评结果:RE
  • 用时:155ms
  • 内存:99144kb
  • [2024-11-07 09:25:50]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
template<typename T>void ckmax(T& x,T y){x=max(x,y);}

#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os&,pair<T1,T2>);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){auto n=0u;out<<"{";for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){auto n=0u;out<<"{";((out<<x<<(++n==sizeof...(T)?"":",")),...);},x),out<<"}";}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif

const int maxn=1.4e6+5;

char s[maxn];
int n,h[maxn],id[maxn],sa[maxn],rk[maxn],buc[maxn],m,p,rk0[maxn];
int st[__lg(maxn)+5][maxn];

void getsa(){
	m=130,p=0;
	memset(buc,0,sizeof(int)*(m+3));
	F(i,1,n) buc[ rk[i]=s[i] ]++;
	F(i,1,m) buc[i]+=buc[i-1];
	for(int i=n;i>=1;i--) sa[ buc[rk[i]]-- ]=i;
	for(int w=1;p!=n;w*=2,m=p){
		p=0;
		F(i,1,n) if(i>=n-w+1) id[++p]=i;
		F(i,1,n) if(sa[i]>w) id[++p]=sa[i]-w;
		memset(buc,0,sizeof(buc[0])*(m+3));
		F(i,1,n) buc[ h[i]=rk[id[i]] ]++;
		F(i,1,m) buc[i]+=buc[i-1];
		for(int i=n;i>=1;i--) sa[ buc[h[i]]-- ]=id[i];
		p=0,memcpy(rk0,rk,sizeof(int)*(n+5));
		F(i,1,n) rk[sa[i]]=[w,x=sa[i-1],y=sa[i]](){return rk0[x]==rk0[y] && rk0[x+w]==rk0[y+w];}()? p: ++p;
	}
	F(_,1,n){
		int i=rk[_];
		st[0][i]=max(st[0][rk[_-1]]-1,0);
		while(s[sa[i]+st[0][i]]==s[sa[rk[sa[i]]-1]+st[0][i]]) st[0][i]++;
	}
	F(i,1,__lg(n)) F(j,1,n-(1<<i)+1) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	//F(i,1,n) debug(i,s+sa[i],st[0][i]);
}

int get(int x,int y){
	if(x>y) return n-sa[y]+1;
	int d=__lg(y-x+1);
	return min(st[d][x],st[d][y-(1<<d)+1]);
}

int getfst(pair<int,int> rng){
	if(rng.x>rng.y) return 0;
	int len=rng.y-rng.x+1;
	{
		int l=1,r=rk[rng.x]-1,z=rk[rng.x];
		while(l<=r){
			int mid=(l+r)>>1;
			if(get(mid+1,rk[rng.x])>=len) r=mid-1,z=mid;
			else l=mid+1;
		}
		return z;
	}
}

pair<int,int> getrng(pair<int,int> rng){
	int pos=sa[getfst(rng)];
	int len=rng.y-rng.x+1;
	rng={pos,pos+len-1};
	{
		int l=rk[rng.x],r=n,z=rk[rng.x]-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(get(rk[rng.x]+1,mid)>=len && s[sa[mid]+len]=='$') l=mid+1,z=mid;
			else r=mid-1;
		}
		return {rk[rng.x],z};
	}
}

vector<pair<int,int>> pp;

int qzh[maxn];

int _f(int l,int r){return qzh[getfst({l,r})-1];}
int f(int l,int r){
	return _f(l,r);
	//int ans=0;
	//for(auto i:pp) if(string(s+i.x,s+i.y+1)<string(s+l,s+r+1)) ans++;
	//assert(ans==_f(l,r));
	//return ans;
}
int _c(int l,int r){
	auto rng=getrng({l,r});
	return qzh[rng.y]-qzh[rng.x-1];
}
int c(int l,int r){
	return _c(l,r);
	//int ans=0;
	//for(auto i:pp) if(string(s+i.x,s+i.y+1)==string(s+l,s+r+1)) ans++;
	//assert(ans==_c(l,r));
	//return ans;
}

ll ans;

struct Fentree{
	ll t[maxn];
	void add(int x,int k){for(;x<maxn;x+=x&-x) t[x]+=k;}
	ll query(int x){
		if(!x) return 0;
		ll ans=0;
		for(;x;x-=x&-x) ans+=t[x];
		return ans;
	}
}t;

struct DATA{
	int tim,pos,val;
	bool op;
	friend bool operator<(const DATA& a,const DATA& b){
		if(a.tim!=b.tim) return a.tim<b.tim;
		return a.op<b.op;
	}
};

void solve(int l,int r){
	int cx=c(l,r),fx=f(l,r);
	debug("solve",l,r);
	debug(1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx);
	ans+=1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx;
	vector<DATA> v;
	F(i,l,r-1){
		int cy=c(l,i),o1=getfst({l,i}),o2=getfst({i+1,r});
		ans+=6ll*cy*max(0,fx-f(i+1,r)-c(i+1,r));
		if(o2<o1) ans-=3ll*cy*(cy+1);
		if(o1>o2) ans+=3ll*cy*cy;
		v.pb({o1,o2,cy,0});
		v.pb({o2,o1,cy,1});
	}
	sort(view(v));
	for(auto i:v){
		if(i.op==0) ans-=3ll*(t.query(n)-t.query(i.pos))*i.val;
		else t.add(i.pos,i.val);
	}
	for(auto i:v) if(i.op==1) t.add(i.pos,-i.val);
}

void doit(){
	ans=0;
	memset(s,0,sizeof(int)*(n+3));
	memset(h,0,sizeof(int)*(n+3));
	memset(qzh,0,sizeof(int)*(n+3));
	memset(id,0,sizeof(int)*(n+3));
	memset(sa,0,sizeof(int)*(n+3));
	memset(rk,0,sizeof(int)*(n+3));
	memset(buc,0,sizeof(int)*(n+3));
	memset(rk0,0,sizeof(int)*(n+3));
	for(auto& i:st) memset(i,0,sizeof(int)*(n+3));
	n=0;
	int p;
	cin>>p;
	pp.clear();
	F(i,1,p){
		char ss[maxn];
		cin>>(ss+1);
		int len=strlen(ss+1);
		s[++n]='$';
		F(j,1,len) s[++n]=ss[j];
		pp.pb({n-len+1,n});
	}
	s[++n]='$';
	s[++n]='|';
	getsa();
	for(auto i:pp) qzh[rk[i.x]]++;
	F(i,1,n) qzh[i]+=qzh[i-1];
	for(auto i:pp) solve(i.x,i.y);
	debug(ans);
	cout<<ans/6<<endl;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) doit();
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 76748kb

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: 0ms
memory: 76896kb

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: 0ms
memory: 78648kb

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: 4ms
memory: 76684kb

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: 8ms
memory: 79100kb

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: 0
Accepted
time: 128ms
memory: 86568kb

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:

ok 503 lines

Test #7:

score: 0
Accepted
time: 145ms
memory: 78204kb

input:

503
23
rjyyivdg
n
n
n
n
n
n
n
nmr
n
nmrk
nm
rjyyivdguyiffnvunoxconw
n
n
n
o
lixclcmwthwkrsi
mqluhyypgfkmdvgpzju
n
nmrk
rjy
n
15
jotwxwhaqdxmazhslyouztprzlirisvwvduojb
jot
jotwxw
j
jotwx
jotwx
gohg
j
gdgneodagmdhvvapjh
jotwxw
xs
vurk
vurk
j
xs
7
xrczucnkbemaymvabkkwnn
xrczucnkbemaymvabkkwnn
xrczucnkb...

output:

855
58
35
0
1
56
2
112
1
8465
242
56
110
23
544
0
3
17
29
11
764
20
9
0
4
77
812
35
4
10
32
437
9
2364
3
2
11
2
421
50
4
107
1
62
1120
3
1
16
3970
1147
1026
8
4
85
9
31
61
16
205
2
2
84
238
1
1
51
4
0
16
61
331
4
16
7
0
7
148
10
13
2
1
37
1
67
0
296
1
0
644
32
2
10
0
5
126
3490
4
0
10
331
1216
7921
...

result:

ok 503 lines

Test #8:

score: 0
Accepted
time: 148ms
memory: 78368kb

input:

503
5
ljtolmgjndlwoyjjttak
mihjdhkyfnafwrpeuiuiurusvsnu
ljtolmgjndlwoyjjttak
mihjd
ljtolmgjndlwoyjjttak
25
lhx
lh
lhx
lh
k
lh
kninp
l
lhx
lhx
izeqohkpfuovopebttqaufmmlivd
lhx
lhx
qid
lhx
lh
lhx
lhx
oklb
l
lhx
lhx
lhx
lhx
l
9
mxeonfwpujrilfigjoiyjkzdmi
fezhyrcyqy
mx
fezh
f
dmvfbklnkxmnetib
dmvfbkln
m...

output:

4
1476
27
26
117970
2
105
30
4
737
4
2
19
48
34
434
6
78331
22
23
0
228
56
4
3
305
9
84
132
199
20
3
4057
0
0
20
35
34
48
4
266
14
17
4788
545
28989
0
10
535
84
1
1775
322
11
57
16
15
1331
5
0
10
5
183
8
2
237
10
0
60
20
42
7
10
297
14
210
6254
7
3
0
13
2744
119
47
0
1
68114
17
1
2
1
7
1
2
113
26
0
...

result:

ok 503 lines

Test #9:

score: 0
Accepted
time: 155ms
memory: 99144kb

input:

503
11
wkeoqqqpvmgdv
w
w
w
wkeoqqqpvmgdv
sgrwmsfwclpamgq
wkeoqqqpvm
qkmbyvcxjsh
wkeoqqqpvm
wke
wkeoqqqpvmgdv
7
otd
qelodfwrqeprgyvzbcjljx
qe
qelodfwrqeprgyvzbcjlj
qelodfwrqeprgyvzbcjlj
qelodfwrqeprgyvzbcjlj
c
15
rce
rce
fwq
fwqqfcjrhqot
rceft
jkdrcehfwhqkupe
fwq
r
jkdr
fwq
rceft
rce
fwqqfcjrhqot
fwq...

output:

156
17
213
12
20
1
374
4
0
26
26
3
122
30
4005
24
1385
50
84
44
0
112
42
36
19
887
99
5
9
13
2
5029
52
14
84
116
2
10
4
8
141
9287
822
37
5
13
25
1030
0
2
3
35
81
1
0
1
138
0
578
7
30
636
63
22
2118
863
5377
33
34
10
156
336
1
7
7
4
1793
2
124
13
4
2015
7
23
1
4516
3
17
6
35
13336
9
61
3093
0
1
7
22...

result:

ok 503 lines

Test #10:

score: -100
Runtime Error

input:

1003
3
mpfowyd
mpfowydrivrkjiarwcxwbfqvnktlzcfolbbsgelvcnzeqy
hytzojmfeiwtpquxhneeznbdjjlsptedaorwfsxi
3
nyfcq
nyfcqgrmshiwmgcbukozvetdggebkkychamof
nyfcqgrmshiwmgcbukozvetdggebkkychamofadozdympuejvhdnpi
8
yoeqyfcjsywowdrlzzybjvtycqvizzomc
zci
yoeqyfc
zcinc
yoeqyfcjsywowdrlzzybjvtycqvizzomc
y
zcinc
...

output:


result: