QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#746742 | #9406. Triangle | Huasushis | TL | 160ms | 38000kb | C++17 | 4.1kb | 2024-11-14 15:25:19 | 2024-11-14 15:25:24 |
Judging History
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::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] = std::vector<ull>(len[i] + 1, 0);
rank[i] = std::vector<int>(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: 3ms
memory: 32568kb
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: 5ms
memory: 31152kb
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: 5ms
memory: 32724kb
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: 11ms
memory: 32916kb
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: 33516kb
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: 160ms
memory: 38000kb
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: 109ms
memory: 35232kb
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: 123ms
memory: 35380kb
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: 123ms
memory: 34684kb
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 ...