QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714988#9406. Trianglelzc0115WA 940ms98420kbC++143.6kb2024-11-06 09:40:102024-11-06 09:40:13

Judging History

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

  • [2024-11-06 09:40:13]
  • 评测
  • 测评结果:WA
  • 用时:940ms
  • 内存:98420kb
  • [2024-11-06 09:40:10]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

#define pii pair<int, int>
#define P make_pair

string t[300010];
char s[2000010];

int T, n, m, SA[2000010], rk[40000010], ht[2000010], q[2000010], k[2000010], h[300010], p[2000010];
long long c[2000010], cnt[2000010], tot[2000010], tail;
long long ans;

priority_queue<pii, vector<pii>, greater<pii> > que;

bool cmp(string x, string y){
  return x.size() < y.size();
}

void ins(int x){
  string t = "";
  for(int i = 1; i <= 4; i++){
    t = (char)('A' + x % 26) + t;
    x /= 26;
  }
  for(int i = 0; i < 4; i++){
    s[++n] = t[i];
  }
}

void _SA(){
  for(int i = 1; i <= n; i++) cnt[i] = rk[i] = SA[i] = ht[i] = 0;
  for(int i = 1; i <= (n << 1); i++) rk[i] = 0;
  for(int i = 1; i <= 256; i++) cnt[i] = 0;
  for(int i = 1; i <= n; i++) cnt[s[i]]++;
  for(int i = 1; i <= 256; i++) cnt[i] += cnt[i - 1];
  for(int i = 1; i <= n; i++) rk[i] = cnt[s[i] - 1] + 1;
  for(int i = 1; i <= n; i++) SA[cnt[s[i]]--] = i;
	for(int i = 0; n >> i; i++){
		int TT = (1 << i), t = 0, mx = rk[SA[n]];
		for(int j = n; j > n - TT; j--) q[++t] = j;
		for(int j = 1; j <= n; j++){
			if(SA[j] > TT) q[++t] = SA[j] - TT;
			cnt[j] = 0;
		}
		for(int j = 1; j <= n; j++) cnt[rk[j]]++;
		for(int j = 1; j <= mx; j++) cnt[j] += cnt[j - 1];
		for(int j = n; j; j--) SA[cnt[rk[q[j]]]--] = q[j];
		for(int i = 1; i <= n; i++){
			k[SA[i]] = !(rk[SA[i] + TT] == rk[SA[i - 1] + TT] && rk[SA[i]] == rk[SA[i - 1]]) + k[SA[i - 1]];
		}
		copy(k + 1, k + n + 1, rk + 1);
	}
  for(int i = 1; i <= n; i++){
    if(rk[i] == 1) continue;
    ht[rk[i]] = max(0, ht[rk[i - 1]] - 1);
    while(s[i + ht[rk[i]]] == s[SA[rk[i] - 1] + ht[rk[i]]]) ht[rk[i]]++;
  }
}

void Add(int x, long long y){
  for(; x; x -= (x & -x)){
    c[x] += y;
  }
}

long long Ask(int x){
  long long ans = 0;
  for(; x <= n; x += (x & -x)){
    ans += c[x];
  }
  return ans;
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> T;
  while(T--){
    cin >> m;
    for(int i = 1; i <= m; i++){
      cin >> t[i];
    }
    if(m < 3){
      cout << 0 << "\n";
      continue;
    }        
    sort(t + 1, t + m + 1, cmp);
    n = ans = 0;
    for(int i = 1; i <= m; i++){
      if(i > 1) ins(i - 1);
      h[i] = n + 1;
      for(int j = 0; j < t[i].size(); j++){
        s[++n] = t[i][j];
      }
    }
    ins(m);
    for(int i = 1; i <= n; i++) p[i] = 0;
    for(int i = 1; i <= m; i++) p[h[i]] = i;
    _SA();
    while(!que.empty()) que.pop();
    for(int i = 1; i <= n; i++) c[i] = cnt[i] = 0;
    tail = 0;
    for(int i = 2; i <= n; i++){
      while(tail && t[q[tail]].size() > ht[i]) tail--;
      if(!p[SA[i]]) continue;
      for(int j = 1; j <= tail; j++){
        while(!que.empty() && que.top().first < rk[h[q[j]]]){
          int x = que.top().second;
          que.pop();
          Add(rk[h[q[x]]], -cnt[x]);
        }
        int x = rk[SA[i] + t[q[j]].size()];
        ans += 1ll * Ask(x) * cnt[j];
        if(x < rk[h[q[j]]]) ans -= 1ll * cnt[j] * (cnt[j] + 1) / 2, Add(rk[h[q[j]]], -cnt[j]);
        else if(x < i) que.push(P(x, j));
      }
      while(!que.empty()){
        int x = que.top().second;
        que.pop();
        Add(rk[h[q[x]]], -cnt[x]);
      }
      for(int j = 1; j <= tail; j++){
        int x = rk[SA[i] + t[q[j]].size()];
        if(x < i) Add(rk[h[q[j]]], cnt[j]);
      }
      if(tail && t[q[tail]].size() == t[p[SA[i]]].size()) cnt[tail]++;
      else cnt[++tail] = 1, q[tail] = p[SA[i]];
      Add(i, 1);
    }
    cout << ans << "\n";    
  }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 6ms
memory: 31864kb

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: 31420kb

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: 32908kb

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

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: 99ms
memory: 40876kb

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

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

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: 43ms
memory: 34184kb

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: 0
Accepted
time: 940ms
memory: 98420kb

input:

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

output:

0
1
26
10
66
403
1
265
1025
16
329
4
1219
1
10
70
30
182
60
5
71
1
20
5343
22328
40667
90
6983
66
10
35
20
250
307
913
98
44
5393
56
280
270
3
3
2229
77
17
774
50
5
21
0
208
8
14
185
35
20
11
465
132
176
10
0
10
1704
13
44
141
0
0
5
10
79
17
213
10
108
0
0
289
10
255
27
493
4
1
24
379
30
9
284
173
2...

result:

ok 1003 lines

Test #11:

score: 0
Accepted
time: 563ms
memory: 63724kb

input:

1003
6
exssl
exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx
f
exss
exs
exsslhsuwyemcafatpinzvdeypwjqsnvxlkvmpywgx
7
hzzev
hzzevmltbehnvjfhsz
hzzevmltbe
hzzevmltbehnvjfhszqzobn
hzzevmltbehnvjf
hm
hzzevmltbehnvjfhszqzobn
9
rdx
rdxnxdfcyrdpgwzwtqgtu
rdx
rdxnxdfcyrdpgwzwtqgtu
f
kpotnxntufvd
kpotnxntufvdlmij...

output:

3
19
41
134
107
2
372
0
466
456
20
13
25
339
64
170
1
5
27295
3
1
221
116
11
29
19
1006
16827
16
19863
4
6
5784
3
20
21130
66
1275
100
731
83
3
84
0
32
3
615
207
8
44
245
48
165
18050
128
11
864
21
3
1221
120
51
21
8
247
302
0
1098
0
57
42
20
0
845
1
84
16
4
0
2
836
482
4
12
150
654
1035
142
291
34
...

result:

ok 1003 lines

Test #12:

score: 0
Accepted
time: 433ms
memory: 57272kb

input:

1003
10
lgbpleleme
u
u
uxpwzhga
uxpwzhg
u
uxpwzhgaadltqqpqkbteylath
u
uxpwzhgaadltqqpqkbteylath
uxpwzhgaadltqqpq
9
aqoxfsmqwpafbocodlpdykesadqgiggw
swzjus
oim
aqoxfsmq
aqoxfsmqwpafboc
swzju
nohnsjbdhljarh
swzjusx
aqoxf
20
mbdiqaartewavbbwbhftzwxm
k
mbdiqaartewavbbwbhftzwxm
kx
kxs
kxsqv
kx
kx
kxsqv
k...

output:

70
0
290
10
604
1770
2
913
1
165
16
316
4
169
26
3
36
2
1549
2
13
15
21
14
109
34
16
1889
132
1700
1
96
17
436
2
0
6183
4144
0
4
50
4
10
5
4
4
78
10
16
97
16
50204
15871
350
3
865
46
7
0
73
38
46
29
1946
65
22088
7
91
43
310
1806
0
50
4
17
38725
262
50
0
304
141
35
50
0
22760
2973
14
410
1112
20
703...

result:

ok 1003 lines

Test #13:

score: -100
Wrong Answer
time: 384ms
memory: 61632kb

input:

1003
7
amhy
ncfsepqjimkaxkvlsqw
bgk
ncfsepqjim
n
amhyderccfrcdclbgrhxospemrlwctcnogb
ncfsepqjimkaxkvlsqwzxubaz
15
ul
k
cqm
kuixi
ovrwzbvkvkzfuqtxooevyvuayhupn
o
kuixi
ulihj
k
k
kzlmrtwddplvqvakmeda
ku
k
kzlmrtwddplvqvakmeda
k
15
mf
dwhth
cwkbrvykvcvqltdovbcy
dwhth
dwht
dwhth
cwkbrvykvcvqltdovbcy
dwh...

output:

4
58
203
10
8614
17
20
0
0
4
43987
18
164
144
35
412
3
19
20
51
50
0
4
16
37
1
4
14
8
526
197
71
20
26
20
35
55
16
0
3667
274
2024
4
33
19492
435
1
2
10
10
22631
32
690
1
0
13
166
561
6
67
10
33
286
4
1
89
11
18
12266
26
23
280
286
16
400
102
0
10
46
40
1
84
27
14
5699
105
197
39
818
36
6
29491
4
17...

result:

wrong answer 624th lines differ - expected: '1998', found: '2229'