Submission #1070411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070411		windowwife	Selling RNA Strands (JOI16_selling_rna)	C++17	60 / 100	1608 ms	557808 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 3e6 + 2, mod = 998244353;
int n, res, numnode, m;
string s[maxn], p, q;
vector<int> ok;
struct Node
{
    int child[26];
    int l, r;
    vector<int> v;
}node[maxn];
struct PrefixTrie
{
    void add (int idx, string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0)
            {
                cur = node[cur].child[c - 'A'] = ++numnode;
                node[cur].l = node[cur].r = idx;
            }
            else
            {
                cur = node[cur].child[c - 'A'];
                node[cur].r = idx;
            }
        }
    }
    pair<int, int> find (string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) return {0, 0};
            cur = node[cur].child[c - 'A'];
        }
        return {node[cur].l, node[cur].r};
    }
}ptrie;
struct SuffixTrie
{
    void add (int idx, string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) cur = node[cur].child[c - 'A'] = ++numnode;
            else cur = node[cur].child[c - 'A'];
            node[cur].v.push_back(idx);
        }
    }
    vector<int> find (string &s)
    {
        int cur = 0;
        for (char c : s)
        {
            if (node[cur].child[c - 'A'] == 0) return {};
            cur = node[cur].child[c - 'A'];
        }
        return node[cur].v;
    }
}strie;
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) ptrie.add(i, s[i]);
    for (int i = 1; i <= n; i++)
    {
        reverse(s[i].begin(), s[i].end());
        strie.add(i, s[i]);
    }
    while (m--)
    {
        cin >> p >> q;
        reverse(q.begin(), q.end());
        auto [L, R] = ptrie.find(p);
        ok = strie.find(q);
        if (L == 0 || ok.empty())
        {
            cout << 0 << '\n';
            continue;
        }
        ok.push_back(n + 1);
        cout << upper_bound(ok.begin(), ok.end(), R) - lower_bound(ok.begin(), ok.end(), L) << '\n';
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40