답안 #760900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760900 2023-06-18T20:40:00 Z Valera_Grinenko Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
1476 ms 230048 KB
#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

const int max_n_st = 2e6 * 4 + 2e5 + 42;

template<typename T>
struct fenw_sum {
    T sum[max_n_st];

    void _add(int point, T x) {
        for(; point < max_n_st; point += (point & -point)) sum[point] += x;
    }

    void add(int point, T x) {
        _add(point + 1, x);
    }

    T _get(int point) {
        T res = 0;
        for(; point > 0; point -= (point & -point)) res += sum[point];
        return res;
    }

    T get(int l, int r) {
        return _get(r + 1) - _get(l);
    }

};

const int max_len = 1e5 + 42;

vector<int> queries[max_len];

const int max_n = 1e5 + 42;

int L[max_n], R[max_n];

void solve() {
    int n, m;
    cin >> n >> m;
    string conc;
    vector<string> s(n), r(m), q(m);
    vector<int> st1(n), st2(m);
    vector<pair<int, int> > av;
    for(int i = 0; i < n; i++) {
        cin >> s[i];
        conc += s[i];
        st1[i] = len(conc);
        conc += s[i];
        conc += '.';
        av.pb({len(s[i]), st1[i]});
    }
    sort(all(av)); reverse(all(av));
    vector<int> here(max_n_st, -1);
    for(int i = 0; i < m; i++) {
        cin >> r[i] >> q[i];
        st2[i] = len(conc);
        conc += q[i]; conc += r[i];
        conc += '.';
        queries[len(q[i])].pb(i);
    }
    auto sufarr = atcoder::suffix_array(conc);
    auto lcp = atcoder::lcp_array(conc, sufarr);
    reverse(all(lcp)); lcp.pb(0); reverse(all(lcp));
    fenw_sum<int> fwsum = {};
    vector<int> inv(len(conc));
    for(int i = 0; i < len(conc); i++) {
        inv[sufarr[i]] = i;
    }
    for(int i = 0; i < m; i++) here[inv[st2[i]]] = i;
    vector<pair<int, int> > st;
    st.pb({-1e9, -1});
    for(int i = 0; i < len(conc); i++) {
        if(i - 1 >= 0) {
            while(!st.empty() && st.back().fi >= lcp[i]) {
                st.pop_back();
            }
            st.push_back({lcp[i], i - 1});
        }
        st.pb({1e9, i});
        if(here[i] != -1) {
            auto pos = lower_bound(all(st), pair<int, int>{len(r[here[i]]) + len(q[here[i]]), -1}) - st.begin() - 1;
            L[here[i]] = st[pos].se + 1;
        }
//        cout << lcp[i] << ' ';
    }
//    for(auto& x : lcp) cout << x << ' ';
//    cout << '\n';
    st.clear();
    st.pb({-1e9, len(conc)});
    for(int i = len(conc) - 1; i >= 0; i--) {
        if(i + 1 < len(conc)) {
            while(!st.empty() && st.back().fi >= lcp[i + 1]) {
                st.pop_back();
            }
            st.push_back({lcp[i + 1], i + 1});
        }
        st.pb({1e9, i});
//        for(auto& x : st) cout << x.fi << ' ' << ' ' << x.se << ',';
//        cout << '\n';
        if(here[i] != -1) {
            auto pos = lower_bound(all(st), pair<int, int>{len(r[here[i]]) + len(q[here[i]]), -1}) - st.begin() - 1;
            R[here[i]] = st[pos].se - 1;
        }
    }
    for(int i = 0; i < n; i++) fwsum.add(inv[st1[i]], 1);
    vector<int> ans(m, -1);
    for(int len = 1; len < max_len; len++) {
        for(auto& x : av) fwsum.add(inv[x.se - (len - 1)], -1);
        while(!av.empty() && av.back().fi < len) av.pop_back();
        for(auto& x : av) fwsum.add(inv[x.se - len], 1);
        for(auto& curq : queries[len]) {
//            cout << curq << ' ' << L[curq] << ' ' << R[curq] << '\n';
            ans[curq] = fwsum.get(L[curq], R[curq]);
        }
    }
    for(int i = 0; i < m; i++) cout << ans[i] << '\n';
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 66904 KB Output is correct
2 Correct 24 ms 66944 KB Output is correct
3 Correct 25 ms 66828 KB Output is correct
4 Correct 24 ms 66808 KB Output is correct
5 Correct 24 ms 66900 KB Output is correct
6 Correct 24 ms 66828 KB Output is correct
7 Correct 23 ms 66876 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1476 ms 198708 KB Output is correct
2 Correct 1447 ms 199796 KB Output is correct
3 Correct 1241 ms 199448 KB Output is correct
4 Correct 1231 ms 200648 KB Output is correct
5 Correct 943 ms 152308 KB Output is correct
6 Correct 916 ms 152980 KB Output is correct
7 Correct 919 ms 190696 KB Output is correct
8 Correct 1322 ms 209488 KB Output is correct
9 Correct 1444 ms 208668 KB Output is correct
10 Correct 745 ms 164020 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 83436 KB Output is correct
2 Correct 94 ms 80176 KB Output is correct
3 Correct 99 ms 82228 KB Output is correct
4 Correct 94 ms 81616 KB Output is correct
5 Correct 90 ms 79172 KB Output is correct
6 Correct 116 ms 82180 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 66904 KB Output is correct
2 Correct 24 ms 66944 KB Output is correct
3 Correct 25 ms 66828 KB Output is correct
4 Correct 24 ms 66808 KB Output is correct
5 Correct 24 ms 66900 KB Output is correct
6 Correct 24 ms 66828 KB Output is correct
7 Correct 23 ms 66876 KB Output is correct
8 Correct 1476 ms 198708 KB Output is correct
9 Correct 1447 ms 199796 KB Output is correct
10 Correct 1241 ms 199448 KB Output is correct
11 Correct 1231 ms 200648 KB Output is correct
12 Correct 943 ms 152308 KB Output is correct
13 Correct 916 ms 152980 KB Output is correct
14 Correct 919 ms 190696 KB Output is correct
15 Correct 1322 ms 209488 KB Output is correct
16 Correct 1444 ms 208668 KB Output is correct
17 Correct 745 ms 164020 KB Output is correct
18 Correct 99 ms 83436 KB Output is correct
19 Correct 94 ms 80176 KB Output is correct
20 Correct 99 ms 82228 KB Output is correct
21 Correct 94 ms 81616 KB Output is correct
22 Correct 90 ms 79172 KB Output is correct
23 Correct 116 ms 82180 KB Output is correct
24 Correct 1259 ms 206488 KB Output is correct
25 Correct 1228 ms 208000 KB Output is correct
26 Correct 1244 ms 198668 KB Output is correct
27 Correct 1236 ms 201372 KB Output is correct
28 Correct 1292 ms 230048 KB Output is correct
29 Correct 832 ms 171600 KB Output is correct