Submission #549684

#	Time	Username	Problem	Language	Result	Execution time	Memory
549684		colossal_pepe	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	412 ms	192412 KiB

selling_rna

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cstring>
using namespace std;

unordered_map<char, int> id = {{'A', 0}, {'C', 1}, {'G', 2}, {'U', 3}};

struct Node {
    int children[4];
    vector<int> e;
    Node() {
        memset(children, -1, sizeof(children));
    }
};

struct Trie {
    vector<Node> trie;
    Trie() {
        trie = {Node()};
    }
    void insert(const string& s, int x) {
        int node = 0, sz = s.size();
        trie[node].e.push_back(x);
        for (int i = 0; i < sz; i++) {
            if (trie[node].children[id[s[i]]] == -1) {
                trie[node].children[id[s[i]]] = trie.size();
                trie.push_back(Node());
            }
            node = trie[node].children[id[s[i]]];
            trie[node].e.push_back(x);
        }
    }
    pair<int, int> getRange(const string& s) {
        int node = 0, sz = s.size();
        for (int i = 0; i < sz; i++) {
            if (trie[node].children[id[s[i]]] == -1) return {-1, -1};
            node = trie[node].children[id[s[i]]];
        }
        return {trie[node].e.front(), trie[node].e.back()};
    }
    int countElementsInRange(const string& s, pair<int, int> p) {
        int l = p.first, r = p.second;
        int node = 0, sz = s.size();
        for (int i = 0; i < sz; i++) {
            if (trie[node].children[id[s[i]]] == -1) return 0;
            node = trie[node].children[id[s[i]]];
        }
        return upper_bound(trie[node].e.begin(), trie[node].e.end(), r) - lower_bound(trie[node].e.begin(), trie[node].e.end(), l);
    }
};

int n, m;
vector<pair<string, string>> s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    s.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i].first;
        s[i].second = s[i].first;
        reverse(s[i].second.begin(), s[i].second.end());
    }
    sort(s.begin(), s.end(), [](const pair<string, string>& p1, const pair<string, string>& p2) {
        return p1.first < p2.first;
    });
    Trie trie_pref = Trie();
    Trie trie_suf = Trie();
    for (int i = 0; i < n; i++) {
        trie_pref.insert(s[i].first, i);
        trie_suf.insert(s[i].second, i);
    }
    for (int i = 0; i < m; i++) {
        string pref, suf;
        cin >> pref >> suf;
        reverse(suf.begin(), suf.end());
        pair<int, int> range = trie_pref.getRange(pref);
        if (range.first == -1) {
            cout << 0 << '\n';
        } else {
            cout << trie_suf.countElementsInRange(suf, range) << '\n';
        }
    }
    return 0;
}

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