Submission #847313

#	Time	Username	Problem	Language	Result	Execution time	Memory
847313		Szil	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	217 ms	196436 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using RNA = vector<int>;

const int MAXN = 100'001;

struct Trie {

    static constexpr int N = 4;

    struct TrieNode {
        TrieNode *next[N];
        int st = MAXN;
        int en = -1;
    };

    TrieNode *root;

    Trie() {
        root = new TrieNode();
    }

    void add_string(const RNA &s, int index) {
        TrieNode *curr = root;
        for (int c : s) {
            if (!curr->next[c]) {
                curr->next[c] = new TrieNode();
            }

            curr = curr->next[c];
            curr->st = min(curr->st, index);
            curr->en = max(curr->en, index);
        }
    }

    pair<int, int> get_bounds(const RNA &s) const {
        TrieNode *curr = root;
        for (int c : s) {
            if (!curr->next[c]) {
                return {-1, -1};
            }

            curr = curr->next[c];
        }
        return {curr->st, curr->en};
    }
};

struct PersistentTrie {

    static constexpr int N = 4;

    struct PersistentTrieNode {
        PersistentTrieNode *next[N];
        int cnt = 0;

        PersistentTrieNode *get_copy() {
            PersistentTrieNode *res = new PersistentTrieNode();

            res->cnt = cnt;
            for (int i = 0; i < N; i++) {
                res->next[i] = next[i];
            }

            return res;
        }
    };

    vector<PersistentTrieNode*> roots;

    PersistentTrie() {
        roots.emplace_back(new PersistentTrieNode());
    }

    void add_string(const RNA &s) {
        roots.emplace_back(roots.back()->get_copy());
        PersistentTrieNode *curr = roots.back();

        for (int i = s.size() - 1; i >= 0; i--) {
            if (curr->next[s[i]]) {
                curr->next[s[i]] = curr->next[s[i]]->get_copy();
            } else {
                curr->next[s[i]] = new PersistentTrieNode();
            }

            curr = curr->next[s[i]];
            curr->cnt++;
        }
    }

    int get_count(const RNA &s, int time) {
        if (time < 0) return 0;

        PersistentTrieNode *curr = roots[time];

        for (int i = s.size() - 1; i >= 0; i--) {
            if (!curr->next[s[i]]) {
                return 0;
            }

            curr = curr->next[s[i]];
        }
        
        return curr->cnt;
    }
};

RNA string_to_rna(const string &s) {
    RNA res;
    for (char c : s) {
        if (c == 'A') {
            res.emplace_back(0);
        } else if (c == 'G') {
            res.emplace_back(1);
        } else if (c == 'C') {
            res.emplace_back(2);
        } else if (c == 'U') {
            res.emplace_back(3);
        }
    }
    return res;
}

void solve() {
    int n, q; cin >> n >> q;
    vector<RNA> v(n+1);
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        v[i] = string_to_rna(s);
    }
    sort(v.begin(), v.end());

    Trie trie;
    PersistentTrie ptrie;

    for (int i = 1; i <= n; i++) {
        trie.add_string(v[i], i);
        ptrie.add_string(v[i]);
    }

    while (q--) {
        string as, bs; cin >> as >> bs;
        RNA a = string_to_rna(as);
        RNA b = string_to_rna(bs);

        auto [l, r] = trie.get_bounds(a);
        int ans = ptrie.get_count(b, r) - ptrie.get_count(b, l-1);
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();    
    return 0;
}

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