Submission #682081

#	Time	Username	Problem	Language	Result	Execution time	Memory
682081		Pannda	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	281 ms	178536 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

struct Trie {
    vector<array<int, 4>> trie;
    vector<vector<int>> mem;

    Trie() : trie(1), mem(1) {}

    void add(int u, string &s, int i) {
        for (auto c : s) {
            if (!trie[u][c]) {
                trie[u][c] = trie.size();
                trie.push_back({});
                mem.push_back({});
            }
            u = trie[u][c];
            mem[u].push_back(i);
        }
    }

    int get(int u, string &s) {
        for (auto c : s) {
            if (!trie[u][c]) {
                return 0;
            }
            u = trie[u][c];
        }
        return u;
    }
};

void alter(string &s) {
    for (auto &ch : s) {
        if (ch == 'A') ch = 0;
        if (ch == 'G') ch = 1;
        if (ch == 'C') ch = 2;
        if (ch == 'U') ch = 3;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    Trie pref, suff;
    vector<string> s(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
        alter(s[i]);
    }

    sort(s.begin(), s.end());

    for (int i = 0; i < n; i++) {
        pref.add(0, s[i], i);
        reverse(s[i].begin(), s[i].end());
        suff.add(0, s[i], i);
    }

    while (q--) {
        string p, s;
        cin >> p >> s;

        alter(p);
        alter(s);
        reverse(s.begin(), s.end());
        int pid = pref.get(0, p);
        int sid = suff.get(0, s);

        int l = pref.mem[pid].front(), r = pref.mem[pid].back();
        cout << upper_bound(suff.mem[sid].begin(), suff.mem[sid].end(), r) - lower_bound(suff.mem[sid].begin(), suff.mem[sid].end(), l) << '\n';
    }
}

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