답안 #760858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760858 2023-06-18T18:27:40 Z Valera_Grinenko Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
1500 ms 346840 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 * 5;

template<typename T>
struct segment_tree_min {
    T mn[4 * max_n_st];

    void build(int v, int l, int r, vector<T>& a) {
        if (l == r) {
            if(l < len(a)) mn[v] = a[l];
            else mn[v] = -1;
            return;
        }
        int mid = (l + r) / 2;
        build(2 * v, l, mid, a);
        build(2 * v + 1, mid + 1, r, a);
        mn[v] = min(mn[2 * v], mn[2 * v + 1]);
    }

    void update(int v, int l, int r, int pos, T value) {
        if (l == r) {
            mn[v] = value;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2 * v, l, mid, pos, value);
        } else {
            update(2 * v + 1, mid + 1, r, pos, value);
        }
        mn[v] = min(mn[2 * v], mn[2 * v + 1]);
    }

    T get_min(int v, int tl, int tr, int l, int r) {
        if (tl == l && tr == r) {
            return mn[v];
        }
        int mid = (tl + tr) / 2;
        if (r <= mid) {
            return get_min(2 * v, tl, mid, l, r);
        } else if (l > mid) {
            return get_min(2 * v + 1, mid + 1, tr, l, r);
        }
        return min(get_min(2 * v, tl, mid, l, mid), get_min(2 * v + 1, mid + 1, tr, mid + 1, r));
    }
};

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];

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));
    segment_tree_min<int> stmn = {}; stmn.build(1, 0, max_n_st - 1, 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 < 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]) {
            int need = len(r[curq]) + len(q[curq]);
            int L = -1, R = -1;
            int lb = 0, rb = inv[st2[curq]];
            while(lb < rb) {
                int mb = (lb + rb) / 2;
                if(stmn.get_min(1, 0, max_n_st - 1, mb + 1, inv[st2[curq]]) < need) lb = mb + 1;
                else rb = mb;
            }
            L = lb;
            lb = inv[st2[curq]], rb = len(conc) - 1;
            while(lb < rb) {
                int mb = (lb + rb + 1) / 2;
                if(stmn.get_min(1, 0, max_n_st - 1, inv[st2[curq]] + 1, mb) < need) rb = mb - 1;
                else lb = mb;
            }
            R = lb;
//            cout << curq << '\n';
//            cout << L << ' ' << R << '.' << inv[st2[curq]] << '\n';
            ans[curq] = fwsum.get(L, R);
        }
    }
    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 119 ms 198416 KB Output is correct
2 Correct 118 ms 198368 KB Output is correct
3 Correct 119 ms 198288 KB Output is correct
4 Correct 127 ms 198304 KB Output is correct
5 Correct 120 ms 198412 KB Output is correct
6 Correct 129 ms 198404 KB Output is correct
7 Correct 119 ms 198416 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1447 ms 334136 KB Output is correct
2 Correct 1351 ms 335272 KB Output is correct
3 Correct 1416 ms 334880 KB Output is correct
4 Correct 1211 ms 335980 KB Output is correct
5 Correct 982 ms 286280 KB Output is correct
6 Correct 1036 ms 286940 KB Output is correct
7 Correct 869 ms 327636 KB Output is correct
8 Correct 1277 ms 346840 KB Output is correct
9 Correct 1401 ms 346004 KB Output is correct
10 Correct 728 ms 298952 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 441 ms 215344 KB Output is correct
2 Correct 360 ms 212012 KB Output is correct
3 Correct 389 ms 214080 KB Output is correct
4 Correct 348 ms 213484 KB Output is correct
5 Correct 328 ms 211004 KB Output is correct
6 Correct 394 ms 214048 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 198416 KB Output is correct
2 Correct 118 ms 198368 KB Output is correct
3 Correct 119 ms 198288 KB Output is correct
4 Correct 127 ms 198304 KB Output is correct
5 Correct 120 ms 198412 KB Output is correct
6 Correct 129 ms 198404 KB Output is correct
7 Correct 119 ms 198416 KB Output is correct
8 Correct 1447 ms 334136 KB Output is correct
9 Correct 1351 ms 335272 KB Output is correct
10 Correct 1416 ms 334880 KB Output is correct
11 Correct 1211 ms 335980 KB Output is correct
12 Correct 982 ms 286280 KB Output is correct
13 Correct 1036 ms 286940 KB Output is correct
14 Correct 869 ms 327636 KB Output is correct
15 Correct 1277 ms 346840 KB Output is correct
16 Correct 1401 ms 346004 KB Output is correct
17 Correct 728 ms 298952 KB Output is correct
18 Correct 441 ms 215344 KB Output is correct
19 Correct 360 ms 212012 KB Output is correct
20 Correct 389 ms 214080 KB Output is correct
21 Correct 348 ms 213484 KB Output is correct
22 Correct 328 ms 211004 KB Output is correct
23 Correct 394 ms 214048 KB Output is correct
24 Correct 1397 ms 341944 KB Output is correct
25 Execution timed out 1570 ms 343596 KB Time limit exceeded
26 Halted 0 ms 0 KB -