QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721935#9406. TriangleguosounCompile Error//C++176.2kb2024-11-07 17:14:442024-11-07 17:14:45

Judging History

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

  • [2024-11-07 17:14:45]
  • 评测
  • [2024-11-07 17:14:44]
  • 提交

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) {
    if (i == j && !p) return !!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 (a == c) return !!1;
    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[id[p]], idx[i]) != l) return std::make_pair(p, p - 1);
    int pp = p;
    for (int j = 20; ~j; j--) {
      if (pp + (1 << j) < n && sa.lcp(idx[id[pp + (1 << j)]], idx[i]) == l)
        pp += 1 << j;
    }
    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) {
    if (mp[s[i]] < 2) continue;
    auto t =
        std::lower_bound(id.begin(), id.end(), std::make_pair(i, i), cmp2) -
        id.begin() - mp[s[i]];
    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;
  }
  std::vector<int> stk;
  // cpp_dump(ans);
  // return;
  std::vector<std::vector<int>> hope(n);
  for (int i = 0; i < (int)uid.size(); i++) {
    int a = uid[i];
    while (stk.size() && sa.lcp(idx[stk.back()], idx[a]) != len[stk.back()])
      stk.pop_back();
    for (int p : stk) hope[p].push_back(a);
    stk.push_back(a);
  }
  stk.clear();
  for (int i = 0; i < (int)uid.size(); i++) {
    int a = uid[i];
    while (stk.size() && sa.lcp(idx[stk.back()], idx[a]) != len[stk.back()])
      stk.pop_back();
    for (int b : hope[a]) {
      ll c = (ll)mp[s[a]] * mp[s[b]];
      cpp_dump(a, b, c);
      if (sa.lcp(idx[a], idx[b]) != len[a]) continue;
      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) * c;
      auto [l2, r2] = find(a);
      chkmax<int>(l2, find(b).second + 1);
      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));
      // cpp_dump(a, b, l2, r2, cmp2(1, {2, 1}));
      ans += std::max(r2 - l2 + 1, 0) * c;
      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) * c;
      ans -= (stk.end() - std::upper_bound(
                             stk.begin(), stk.end(), b,
                             [&](auto x, auto y) { return cmp(x, y, len[a]); })) * c;
      // cpp_dump(stk, ans);
    }
    for (int j = 0; j < mp[s[a]]; j++) stk.push_back(a);
  }
  std::cout << ans << '\n';
}
int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  int t;
  std::cin >> t;
  while (t--) mian();
}

詳細信息

answer.code: In function ‘void mian()’:
answer.code:141:7: error: ‘cpp_dump’ was not declared in this scope
  141 |       cpp_dump(a, b, c);
      |       ^~~~~~~~