Submission #46596008

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

struct Fenwick {
  int n;
  vector<int> a;
  Fenwick(int n_) : n(n_ + 1) { a.resize(n); }
  void Change(int x, int dx) {
    while (x < n) {
      a[x] += dx;
      x |= (x + 1);
    }
  }
  int GetSum(int x) {
    int res = 0;
    while (x >= 0) {
      res += a[x];
      x = (x & (x + 1)) - 1;
    }
    return res;
  }
  int RangeSum(int l, int r) {
    auto res = GetSum(r);
    if (l > 0) res -= GetSum(l - 1);
    return res;
  }
};

int Go(string& a, string& b) {
  int i = 0, j = 0, res = 0;
  while (i < (int)a.length() && j < (int)b.length()) {
    if (a[i] == b[j]) {
      res++, i++, j++;
    } else {
      j++;
    }
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  string t;
  cin >> n >> t;
  string tr = t;
  reverse(tr.begin(), tr.end());
  int len = t.length();
  vector<string> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  int64 ans = 0;

  auto Work = [&](int ttt) {
    Fenwick fw(500005);
    for (int i = 0; i < n; i++) {
      auto s = a[i];
      int l = Go(t, s);
      reverse(s.begin(), s.end());
      int r = Go(tr, s);
      if (ttt) fw.Change(r, 1);
      ans += fw.RangeSum(len - l, 500000);
      if (!ttt) fw.Change(r, 1);
      debug(i, l, r, ans);
    }
  };
  Work(0);
  reverse(a.begin(), a.end());
  Work(1);
  cout << ans << '\n';

  return 0;
}

Submission Info

Judge Result