QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721333 | #9406. Triangle | guosoun | WA | 1ms | 3680kb | C++17 | 5.3kb | 2024-11-07 15:53:00 | 2024-11-07 15:53:01 |
Judging History
answer
#include <bits/stdc++.h>
// #include "../cpp-dump/cpp-dump.hpp"
template <class T>
void chkmin(T &x, const T &y) {
if (x > y) x = y;
}
template <class T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
using ll = long long;
using std::cerr;
struct suffix_array {
std::vector<int> sa, rk;
std::array<std::vector<int>, 20> st;
suffix_array(std::vector<int> a) {
int n = a.size();
sa.resize(n), rk.resize(n * 2, -1);
std::vector<int> tmp(n), cnt(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int x, int y) { return a[x] < a[y]; });
rk[sa[0]] = 0;
for (int i = 1; i < n; i++)
rk[sa[i]] = rk[sa[i - 1]] + (a[sa[i]] != a[sa[i - 1]]);
for (int w = 1;; w <<= 1) {
int l = 0;
for (int i = n - w; i < n; i++) tmp[l++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= w) tmp[l++] = sa[i] - w;
for (int i = 0; i < n; i++) {
cnt[rk[sa[i]]] = i;
}
for (int i = n - 1; i >= 0; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i - 1]] + (rk[sa[i - 1]] != rk[sa[i]] ||
rk[sa[i - 1] + w] != rk[sa[i] + w]);
std::copy_n(tmp.begin(), n, rk.begin());
if (rk[sa[n - 1]] == n - 1) break;
}
st[0].resize(n), rk.resize(n), a.push_back(-1);
for (int i = 0, k = 0; i < n; i++) {
if (k) k--;
if (rk[i] == 0) continue;
while (a[i + k] == a[sa[rk[i] - 1] + k]) k++;
st[0][rk[i]] = k;
}
for (int i = 1; i < 20; i++) {
st[i].resize(n);
for (int j = 0; j + (1 << i) - 1 < n; j++)
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
int lcp(int i, int j) {
if (i == j) return (int)sa.size() - i;
i = rk[i], j = rk[j];
if (i > j) std::swap(i, j);
i++;
int k = std::__lg(j - i + 1);
return std::min(st[k][i], st[k][j - (1 << k) + 1]);
}
};
void mian() {
int n;
std::cin >> n;
std::vector<std::string> s(n);
std::vector<int> ve, idx(n), len(n);
for (int i = 0; i < n; i++) {
std::cin >> s[i];
ve.push_back(1e9 + i), idx[i] = ve.size();
for (char c : s[i]) ve.push_back(c);
len[i] = s[i].size(), s[i].push_back('-');
}
suffix_array sa(ve);
auto cmp = [&](int i, int j, int p = 0) {
int l = sa.lcp(idx[i] + p, idx[j]);
return s[i][l + p] < s[j][l];
};
auto cmp2 = [&](int c, std::pair<int, int> d) { // c < a + b
auto [a, b] = d;
if (sa.lcp(idx[a], idx[c]) == len[a])
return cmp(c, b, len[a]);
return cmp(c, a);
};
std::vector<int> id(n);
std::iota(id.begin(), id.end(), 0);
std::sort(id.begin(), id.end(), cmp);
// cpp_dump(id);
auto find = [&](int i) -> std::pair<int, int> {
auto p = std::upper_bound(id.begin(), id.end(), i, cmp) - id.begin();
int l = len[i];
if (p == n || sa.lcp(idx[p], idx[i]) != l) return std::make_pair(0, -1);
int pp = p;
for (int i = 20; ~i; i--)
if (pp + (1 << i) < n && sa.lcp(idx[pp + (1 << i)], idx[i]) == l)
pp += 1 << i;
return std::make_pair(p, pp);
};
std::vector<int> uid;
std::unordered_map<std::string, int> mp;
for (int i : id) {
if (mp.count(s[i]))
mp[s[i]] += 1;
else
mp[s[i]] = 1, uid.push_back(i);
}
ll ans = 0;
for (int i : uid) {
auto t =
std::lower_bound(id.begin(), id.end(), std::make_pair(i, i), cmp2) -
id.begin();
ans += (ll)mp[s[i]] * (mp[s[i]] - 1) / 2 * t;
ans -= (ll)mp[s[i]] * (mp[s[i]] - 1) * (mp[s[i]] - 2) / 6 * 2;
}
for (int i = 0; i < (int)uid.size(); i++) {
int a = uid[i];
for (int j = i + 1; j < (int)uid.size(); j++) {
int b = uid[j];
if (sa.lcp(idx[a], idx[b]) != len[a]) break;
auto [l1, r1] = find(b);
chkmin<int>(r1, std::max(std::lower_bound(id.begin(), id.end(),
std::make_pair(a, b), cmp2) -
id.begin() - 1,
std::lower_bound(id.begin(), id.end(),
std::make_pair(b, a), cmp2) -
id.begin() - 1));
ans += std::max(r1 - l1 + 1, 0);
auto [l2, r2] = find(a);
chkmax<int>(l2, std::upper_bound(id.begin(), id.end(), b, cmp) - id.begin());
chkmin<int>(r2, std::max(std::lower_bound(id.begin(), id.end(),
std::make_pair(a, b), cmp2) -
id.begin() - 1,
std::lower_bound(id.begin(), id.end(),
std::make_pair(b, a), cmp2) -
id.begin() - 1));
ans += std::max(r2 - l2 + 1, 0);
auto [l3, r3] = std::pair<int, int>(0, std::lower_bound(id.begin(), id.end(), a, cmp) - id.begin() - 1);
chkmax<int>(l3, std::upper_bound(id.begin(), id.end(), b, [&](auto x, auto y) {
return cmp(x, y, len[a]);
}) - id.begin());
ans += std::max(r3 - l3 + 1, 0);
}
}
std::cout << ans << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--) mian();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3680kb
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: -100
Wrong Answer
time: 1ms
memory: 3668kb
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 2 16 22 40 22 40 63 30 35 98 26 11769
result:
wrong answer 3rd lines differ - expected: '0', found: '2'