제출 #1070420

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1070420		windowwife	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	308 ms	557196 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, ok;
string s[maxn], p, q;
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);
        }
    }
    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 cur;
    }
}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 || node[ok].v.empty())
        {
            cout << 0 << '\n';
            continue;
        }
        if (node[ok].v.back() != n + 1) node[ok].v.push_back(n + 1);
        cout << upper_bound(node[ok].v.begin(), node[ok].v.end(), R) - lower_bound(node[ok].v.begin(), node[ok].v.end(), L) << '\n';
    }
}

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