QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#746839#9406. TriangleHuasushisTL 148ms38268kbC++174.2kb2024-11-14 15:40:102024-11-14 15:40:11

Judging History

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

  • [2024-11-14 15:40:11]
  • 评测
  • 测评结果:TL
  • 用时:148ms
  • 内存:38268kb
  • [2024-11-14 15:40:10]
  • 提交

answer

#include <bits/stdc++.h>
#define N 300010
#define M 1000010
using ull = unsigned long long;
const ull mp[26] = {
  1, 3, 7, 9, 11,
  13, 17, 19, 21, 29,
  33, 37, 41, 47, 53,
  59, 61, 63, 67, 71,
  73, 77, 79, 83, 85,
  97
};
const ull bs = 131;
int n;
std::string s[N];
std::vector<ull> hsh[N];
std::vector<int> rank[N];
ull mi[N];
int len[N];
int sx[N];
using pii = std::pair<int, int>;
using t4 = std::tuple<int, int, int, int>;
ull gethsh(int u, int l, int r) {
  ull x = hsh[u][l - 1] * mi[r - l + 1];
  ull y = hsh[u][r];
  return y - x;
}
int getlcp(int x, int xl, int y, int yl) {
  int l = 0, r = std::min(len[x] - xl + 1, len[y] - yl + 1);
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (gethsh(x, xl, xl + mid - 1) == gethsh(y, yl, yl + mid - 1)) l = mid;
    else r = mid - 1;
  }
  return l;
}
bool cmp(pii x, pii y) {
  int lcp = getlcp(x.first, x.second, y.first, y.second);
  if (x.second + lcp > len[x.first] && y.second + lcp > len[y.first] && x.second == 1 && y.second > 1) return 1;
  if (y.second + lcp > len[y.first]) return 0;
  if (x.second + lcp > len[x.first]) return 1;
  return s[x.first][x.second + lcp - 1] < s[y.first][y.second + lcp - 1];
}
std::vector<t4> cha;
std::unordered_map<ull, int> shu, xu, pai;
void cmax(int& x, int y) {
  if (x < y) x = y;
}
using ll = long long;
ll ans;
int tr[N];
void add(int p, int v) {
  while (p <= n) {
    tr[p] += v;
    p += p & -p;
  }
}
int qur(int p) {
  int ans = 0;
  while (p) {
    ans += tr[p];
    p &= (p - 1);
  }
  return ans;
}
void dfs(int l, int r) {
  if (std::get<0>(cha[l]) == std::get<0>(cha[r])) {
    std::sort(cha.begin() + l, cha.begin() + r + 1, [](auto x, auto y){return std::get<1>(x) > std::get<1>(y);});
    return;
  }
  int zhong = (std::get<0>(cha[l]) + std::get<0>(cha[r])) >> 1;
  int mid = l;
  while (std::get<0>(cha[mid + 1]) <= zhong) ++mid;
  dfs(l, mid), dfs(mid + 1, r);
  int i, j;
  for (i = mid + 1, j = l; i <= r; ++i) {
    if (!std::get<3>(cha[i])) continue;
    while (j <= mid && std::get<1>(cha[j]) > std::get<1>(cha[i])) {
      if (!std::get<3>(cha[j]))
      add(std::get<2>(cha[j]), 1);
      ++j;
    }
    ans += 1ll * qur(std::get<2>(cha[i]) - 1) * std::get<3>(cha[i]);
  }
  for (int k = l; k < j; ++k)
  if (!std::get<3>(cha[k]))
  add(std::get<2>(cha[k]), -1);
  std::inplace_merge(cha.begin() + l, cha.begin() + mid + 1, cha.begin() + r + 1, [](auto x, auto y){return std::get<1>(x) > std::get<1>(y);});
}
void gun() {
  ans = 0;
  std::cin >> n;
  std::vector<int> p(n);
  std::vector<pii> q;
  shu.clear(), xu.clear(), pai.clear();
  for (int i = 1; i <= n; ++i) {
    std::cin >> s[i];
    len[i] = s[i].size();
    hsh[i].clear();
    hsh[i].resize(len[i] + 1);
    rank[i].clear();
    rank[i].resize(len[i] + 1);
    for (int j = 1; j <= len[i]; ++j) {
      hsh[i][j] = (hsh[i][j - 1] * bs + mp[s[i][j - 1] - 'a']);
      q.emplace_back(i, j);
    }
    p[i - 1] = i;
  }
  std::sort(p.begin(), p.end(), [](int x, int y){return s[x] < s[y];});
  std::stable_sort(p.begin(), p.end(), [](int x, int y){return s[x] + s[y] < s[y] + s[x];});
  for (int i = 0; i < n; ++i) {
    sx[p[i]] = i + 1;
  }
  std::sort(q.begin(), q.end(), cmp);
  {int js = 0;
  for (auto [i, j] : q) {
    rank[i][j] = ++js;
  }}
  std::sort(p.begin(), p.end(), [](int x, int y){return s[x] < s[y];});
  cha.clear();
  for (int i = 1; i <= n; ++i) {
    int u = p[i - 1];
    cha.emplace_back(i, rank[u][1], sx[u], 0);
    pai[hsh[u][len[u]]] = rank[u][1];
    for (int j = 1; j <= len[u]; ++j) {
      auto hs = hsh[u][j];
      if (!shu.count(hs)) continue;
      cha.emplace_back(i, j == len[u] ? 0 : rank[u][j + 1], xu[hs], shu[hs]);
      
      if (pai[hs] > (j == len[u] ? 0 : rank[u][j + 1])) {
        ll tmp = shu[hs];
        ans -= tmp * (tmp - 1) / 2;
      }
    }
    ++shu[hsh[u][len[u]]];
    cmax(xu[hsh[u][len[u]]], sx[u]);
  }
  dfs(0, cha.size() - 1);
  std::cout << ans << '\n';
}
int main() {
  std::cin.tie(nullptr) -> sync_with_stdio(false);
  for (int i = *mi = 1; i <= 3e5; ++i) mi[i] = mi[i - 1] * bs;
  int T;
  std::cin >> T;
  while (T--) gun();
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 32160kb

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

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

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

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

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: 148ms
memory: 38268kb

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: 98ms
memory: 35244kb

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: 114ms
memory: 35736kb

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

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
Time Limit Exceeded

input:

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

output:


result: