結果
| 問題 | No.515 典型LCP |
| ユーザー |
 Gosu_Hiroo
|
| 提出日時 | 2020-09-22 18:41:27 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 19,966 bytes |
| コンパイル時間 | 3,578 ms |
| コンパイル使用メモリ | 236,204 KB |
| 実行使用メモリ | 35,584 KB |
| 最終ジャッジ日時 | 2024-06-26 08:42:55 |
| 合計ジャッジ時間 | 8,745 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | AC | 2 ms
5,376 KB |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
ソースコード
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Gosu_Hiroo
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<long long>;
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast")
#define G(size_1) vector<vector<int>>(size_1, vector<int>())
#define SZ(x) ((int)(x).size())
#define READ ({ll t;cin >> t;t;})
#define FOR(i, _begin, _end) for (__typeof(_end) end = _end, begin = _begin, i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define REP(i, end) for (__typeof(end) i = 0, _len = (end); i < (_len); i += 1)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define F first
#define S second
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define EB emplace_back
#define PB push_back
#define fcout cout << fixed << setprecision(12)
#define fcerr cerr << fixed << setprecision(12)
#define print(x) cout << (x) << '\n'
#define printE(x) cout << (x) << '\n';
#define fprint(x) cout << fixed << setprecision(12) << (x) << '\n';
# define BYE(a) do { cout << (a) << endl; return ; } while (false)
#ifdef DEBUG
#define DBG(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(cerr,_it, args); }
#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); _err(std::cerr,_it, args); }
#else
#define DBG(args...) {};
#define ERR(args...) {};
#endif
void _err(std::ostream& cerr,istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>
void _err(std::ostream& cerr, istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << " ";
_err(cerr,++it, args...);
}
const double PI = 2 * acos(.0);
const int INF = 0x3f3f3f3f;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T>T ceil(T a, T b) {return (a+b-1)/b;}
template <typename T, typename U>
istream& operator >> (istream& is, pair<T, U>& V) {
is >> V.F >> V.S;
return is;
}
template <typename T>
istream& operator >> (istream& is, vector<T>& V) {
for(auto&& ele : V)is >> ele;
return is;
}
template <typename T>
ostream& operator << (ostream& os, const vector<T> V) {
os << "[";
int cnt = 0;
T curr;
if(!V.empty()){
for (int i = 0; i < V.size() - 1; ++i) {
if(V[i] == curr)cnt ++;
else cnt = 0;
if(cnt == 4)os << "... ";
if(cnt < 4)
os << i << ":" << V[i] << " ";
curr = V[i];
}
os << V.size() - 1 << ":" << V.back();
}
os << "]\n";
return os;
}
template <typename T, typename U>
ostream& operator << (ostream& os, const pair<T,U> P) {
os << "(";
os << P.first << "," << P.second;
os << ")";
return os;
}
template <typename T, typename U>
ostream& operator << (ostream& os, const set<T,U> V) {
os << "{";
if(!V.empty()){
auto it = V.begin();
for (int i = 0; i < V.size() -1; ++i) {
os << *it << " ";
it++;
}
os << *it;
}
os << "}\n";
return os;
}
template <typename K, typename H, typename P>
ostream& operator << (ostream& os, const unordered_set<K, H, P> V) {
os << "{";
if(!V.empty()){
auto it = V.begin();
for (int i = 0; i < V.size() -1; ++i) {
os << *it << " ";
it++;
}
os << *it;
}
os << "}\n";
return os;
}
template <typename K, typename C>
ostream& operator << (ostream& os, const multiset<K, C> V) {
os << "{";
if(!V.empty()){
auto it = V.begin();
for (int i = 0; i < V.size() -1; ++i) {
os << *it << " ";
it++;
}
os << *it;
}
os << "}";
return os;
}
template <typename K, typename T, typename C>
ostream& operator << (ostream& os, const map<K,T,C> V) {
os << "{";
if(!V.empty()){
auto it = V.begin();
for (int i = 0; i < V.size() -1; ++i) {
os << "(";
os << it->first << "," << it->second;
os << ") ";
it++;
}
os << "(";
os << it->first << "," << it->second;
os << ")";
}
os << "}\n";
return os;
}
template <typename K, typename T, typename C>
ostream& operator << (ostream& os, const unordered_map<K,T,C> V) {
os << "{";
if(!V.empty()){
auto it = V.begin();
for (int i = 0; i < V.size() -1; ++i) {
os << "(";
os << it->first << "," << it->second;
os << ") ";
it++;
}
os << "(";
os << it->first << "," << it->second;
os << ")";
}
os << "}\n";
return os;
}
template <typename T>
ostream& operator << (ostream& os, const deque<T> V) {
os << "[";
if (!V.empty()) {
for (int i = 0; i < V.size() - 1; ++i) {
os << V[i] << "->";
}
if (!V.empty())os << V.back();
}
os << "]\n";
return os;
};
template <typename T, typename Cont, typename Comp>
ostream& operator << (ostream& os, const priority_queue<T, Cont, Comp> V) {
priority_queue<T, Cont, Comp> _V = V;
os << "[";
if(!_V.empty()){
while(_V.size() > 1){
os << _V.top() << "->";
_V.pop();
}
os << _V.top();
}
os << "]\n";
return os;
};
template <class F>
struct y_combinator {
F f; // the lambda will be stored here
// a forwarding operator():
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
// we pass ourselves to f, then the arguments.
// the lambda should take the first argument as `auto&& recurse` or similar.
return f(*this, std::forward<Args>(args)...);
}
};
// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> recursive(F&& f){
return {std::forward<F>(f)};
}
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
template <typename T, typename U>
std::vector<T> multi_vector(int n, U v) {
return std::vector<T>(n, v);
}
template <typename U, typename... Args>
auto multi_vector(int n, Args... args) {
auto val = multi_vector<U>(std::forward<Args>(args)...);
return std::vector<decltype(val)>(n, std::move(val));
}
#ifndef ATCODER_SEGTREE_HPP
#define ATCODER_SEGTREE_HPP 1
#include <algorithm>
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_BITOP_HPP
#include <cassert>
#include <vector>
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
std::vector<S> d;
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
S operator[](int p){
assert(0 <= p && p < _n);
return d[p + size];
}
private:
int _n, size, log;
// std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
#endif // ATCODER_SEGTREE_HPP
#ifndef ATCODER_STRING_HPP
#define ATCODER_STRING_HPP 1
#include <numeric>
#include <string>
namespace atcoder {
namespace internal {
std::vector<int> sa_naive(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++;
r++;
}
return l == n;
});
return sa;
}
std::vector<int> sa_doubling(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n), rnk = s, tmp(n);
std::iota(sa.begin(), sa.end(), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
std::sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
std::swap(tmp, rnk);
}
return sa;
}
// SA-IS, linear-time suffix array construction
// Reference:
// G. Nong, S. Zhang, and W. H. Chan,
// Two Efficient Algorithms for Linear Time Suffix Array Construction
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
if (n < THRESHOLD_NAIVE) {
return sa_naive(s);
}
if (n < THRESHOLD_DOUBLING) {
return sa_doubling(s);
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int>& lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa =
sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
} // namespace internal
std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = internal::sa_is(s, upper);
return sa;
}
template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return internal::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return internal::sa_is(s2, 255);
}
// Reference:
// T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
// Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
// Applications
template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
const std::vector<int>& sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
// Reference:
// D. Gusfield,
// Algorithms on Strings, Trees, and Sequences: Computer Science and
// Computational Biology
template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
int n = int(s.size());
if (n == 0) return {};
std::vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
std::vector<int> z_algorithm(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return z_algorithm(s2);
}
} // namespace atcoder
#endif // ATCODER_STRING_HPP
using namespace atcoder;
namespace arg{
using S = int;
S op(S s1, S s2){
return min(s1, s2);
}
S unit(){
return INF;
}
}
using st = segtree<arg::S,arg::op,arg::unit>;
class __test {
public:
void solve(std::istream& cin, std::ostream& cout, std::ostream& cerr) {
int N;cin >> N;
vector<pair<string, int>> strs(N);
REP(i,N){string s;cin >> s;strs[i] = {s, i};}
int M,x,d;cin >> M >> x >> d;
VI I(M), J(M);
REP(k,M){
I[k] = x/(N-1);
J[k] = x%(N-1);
if(I[k]>J[k])swap(I[k],J[k]);
else J[k]++;
x = (x+d)%(N*(N-1));
}
sort(ALL(strs));
VI pos(N);
vector<string> sorted_strs(N);
REP(i,N){
auto [str, ind] = strs[i];
sorted_strs[i] = str;
pos[ind] = i;
}
DBG(sorted_strs)
auto lcp = [&](int i){
int res = 0;
auto str1 = sorted_strs[i], str2 = sorted_strs[i+1];
// DBG(str1, str2)
REP(j,(int)min(SZ(str1), SZ(str2))){
// DBG(j)
if(str1[j] == str2[j])res++;
else break;
}
return res;
};
st mi_st(N-1);
REP(i,N-1){
mi_st.set(i, lcp(i));
DBG(lcp(i))
}
DBG(mi_st.d)
ll ans = 0;
REP(i,M){
ans += mi_st.prod(pos[I[i]], pos[J[i]]);
DBG(I[i], J[i], mi_st.prod(I[i], J[i]));
}
print(ans);
}
};
#undef int
int main() {
__test solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
std::ostringstream err;
in.tie(0); ios::sync_with_stdio(0);
solver.solve(in, out,err);
return 0;
}