Submission #1173023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173023		chikien2009	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	553 ms	269116 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

inline void Convert(string &inp)
{
    for (auto &i : inp)
    {
        if (i == 'A')
        {
            i = '0';
        }
        else if (i == 'C')
        {
            i = '1';
        }
        else if (i == 'G')
        {
            i = '2';
        }
        else
        {
            i = '3';
        }
    }
}

struct NODE
{
    int child[4], end, min_id, max_id;
    vector<int> id;
    inline NODE()
    {
        id.clear();
        end = 0;
        min_id = 1e9;
        max_id = -1e9;
        fill_n(child, 4, -1);
    }
};

class TRIE
{
private:
    vector<NODE> nodes;
    vector<string> sorted;

public:
    inline void Init()
    {
        nodes = {NODE()};
    }
    inline void Add(string inp, int id)
    {
        int cur_node = 0, cur_key, i = 0;
        do
        {
            cur_key = inp[i] - '0';
            if (nodes[cur_node].child[cur_key] == -1)
            {
                nodes[cur_node].child[cur_key] = nodes.size();
                nodes.push_back(NODE());
            }
            cur_node = nodes[cur_node].child[cur_key];
            nodes[cur_node].end += (i == inp.size() - 1);
            nodes[cur_node].min_id = min(nodes[cur_node].min_id, id);
            nodes[cur_node].max_id = max(nodes[cur_node].max_id, id);
            nodes[cur_node].id.push_back(id);
            i++;
        } while (i < inp.size());
    }
    inline void DFS(int ind, string cur)
    {
        for (int i = 0; i < 4; ++i)
        {
            if (nodes[ind].child[i] != -1)
            {
                DFS(nodes[ind].child[i], cur + char(i + '0'));
            }
        }
        for (int i = 0; i < nodes[ind].end; ++i)
        {
            sorted.push_back(cur);
        }
    }
    inline vector<string> GetTrie()
    {
        sorted.clear();
        DFS(0, "");
        return sorted;
    }
    inline pair<int, int> GetRange(string inp)
    {
        int cur_node = 0, cur_key, i = 0;
        do
        {
            cur_key = inp[i] - '0';
            if (nodes[cur_node].child[cur_key] == -1)
            {
                return {-1, -1};
            }
            cur_node = nodes[cur_node].child[cur_key];
            if (i == inp.size() - 1)
            {
                return {nodes[cur_node].min_id, nodes[cur_node].max_id};
            }
            i++;
        } while (i < inp.size());
        return {-1, -1};
    }
    inline int GetNum(string inp, pair<int, int> range)
    {
        int cur_node = 0, cur_key, i = 0;
        do
        {
            cur_key = inp[i] - '0';
            if (nodes[cur_node].child[cur_key] == -1)
            {
                return 0;
            }
            cur_node = nodes[cur_node].child[cur_key];
            if (i == inp.size() - 1)
            {
                return upper_bound(nodes[cur_node].id.begin(), nodes[cur_node].id.end(), range.second) - 
                       lower_bound(nodes[cur_node].id.begin(), nodes[cur_node].id.end(), range.first);
            }
            i++;
        } while (i < inp.size());
        return 0;   
    }
} trie1, trie2;

int n, m;
vector<string> s;
string p, q;

int main()
{
    setup();

    cin >> n >> m;
    s.resize(n);
    trie1.Init();
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i];
        Convert(s[i]);
        trie1.Add(s[i], i);
    }
    s = trie1.GetTrie();
    trie1.Init();
    trie2.Init();
    for (int i = 0; i < n; ++i)
    {
        trie1.Add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        trie2.Add(s[i], i);
    }
    while (m--)
    {
        cin >> p >> q;
        Convert(p);
        Convert(q);
        reverse(q.begin(), q.end());
        cout << trie2.GetNum(q, trie1.GetRange(p)) << "\n";
    }
    return 0;
}

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