답안 #760906

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760906 2023-06-18T20:47:52 Z Valera_Grinenko Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
1427 ms 209292 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];

int inv[max_n_st];

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));
    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<pair<int, int> > here;
    for(int i = 0; i < len(conc); i++) {
        inv[sufarr[i]] = i;
    }
    for(int i = 0; i < m; i++) here.pb({inv[st2[i]], i});
    sort(all(here));
    vector<pair<int, int> > st;
    st.pb({-1e9, -1});
    int here_pos = 0;
    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_pos < len(here) && here[here_pos].fi == i) {
            auto pos = lower_bound(all(st), pair<int, int>{len(r[here[here_pos].se]) + len(q[here[here_pos].se]), -1}) - st.begin() - 1;
            L[here[here_pos].se] = st[pos].se + 1;
            here_pos++;
        }
//        cout << lcp[i] << ' ';
    }
    here_pos = len(here) - 1;
//    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_pos >= 0 && here[here_pos].fi == i) {
            auto pos = lower_bound(all(st), pair<int, int>{len(r[here[here_pos].se]) + len(q[here[here_pos].se]), -1}) - st.begin() - 1;
            R[here[here_pos].se] = st[pos].se - 1;
            here_pos--;
        }
    }
    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 16 ms 34788 KB Output is correct
2 Correct 15 ms 34824 KB Output is correct
3 Correct 15 ms 34836 KB Output is correct
4 Correct 16 ms 34812 KB Output is correct
5 Correct 15 ms 34828 KB Output is correct
6 Correct 16 ms 34816 KB Output is correct
7 Correct 16 ms 34812 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1301 ms 179520 KB Output is correct
2 Correct 1289 ms 181248 KB Output is correct
3 Correct 1199 ms 180516 KB Output is correct
4 Correct 1182 ms 182328 KB Output is correct
5 Correct 948 ms 128352 KB Output is correct
6 Correct 889 ms 128992 KB Output is correct
7 Correct 892 ms 186092 KB Output is correct
8 Correct 1357 ms 208732 KB Output is correct
9 Correct 1348 ms 207820 KB Output is correct
10 Correct 745 ms 153460 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 53008 KB Output is correct
2 Correct 84 ms 48108 KB Output is correct
3 Correct 94 ms 50128 KB Output is correct
4 Correct 85 ms 49488 KB Output is correct
5 Correct 87 ms 48652 KB Output is correct
6 Correct 93 ms 50132 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 34788 KB Output is correct
2 Correct 15 ms 34824 KB Output is correct
3 Correct 15 ms 34836 KB Output is correct
4 Correct 16 ms 34812 KB Output is correct
5 Correct 15 ms 34828 KB Output is correct
6 Correct 16 ms 34816 KB Output is correct
7 Correct 16 ms 34812 KB Output is correct
8 Correct 1301 ms 179520 KB Output is correct
9 Correct 1289 ms 181248 KB Output is correct
10 Correct 1199 ms 180516 KB Output is correct
11 Correct 1182 ms 182328 KB Output is correct
12 Correct 948 ms 128352 KB Output is correct
13 Correct 889 ms 128992 KB Output is correct
14 Correct 892 ms 186092 KB Output is correct
15 Correct 1357 ms 208732 KB Output is correct
16 Correct 1348 ms 207820 KB Output is correct
17 Correct 745 ms 153460 KB Output is correct
18 Correct 105 ms 53008 KB Output is correct
19 Correct 84 ms 48108 KB Output is correct
20 Correct 94 ms 50128 KB Output is correct
21 Correct 85 ms 49488 KB Output is correct
22 Correct 87 ms 48652 KB Output is correct
23 Correct 93 ms 50132 KB Output is correct
24 Correct 1236 ms 185540 KB Output is correct
25 Correct 1255 ms 189088 KB Output is correct
26 Correct 1219 ms 181496 KB Output is correct
27 Correct 1210 ms 183172 KB Output is correct
28 Correct 1427 ms 209292 KB Output is correct
29 Correct 791 ms 139520 KB Output is correct