Submission #1195555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195555		salmakaram	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	191 ms	236864 KiB

selling_rna

#include <bits/stdc++.h>

#define Pc_champs ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;

#define ll long long
//#define int long long

int const N = 1e5 + 2, LOG = 17, N2 = 1e5, M = 1e9 + 7, SQ = 400;

int n, m, idx;
string s[N];
int id[26];

struct Trie {
    struct Node {
        Node *link[4];
        vector<int> indx;
    };

    Node *root = NULL;

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

    void insert(string &str, int j) {
        Node *node = root;
        for (auto i: str) {
            i -= 'A';
            if (node->link[id[i]] == NULL) node->link[id[i]] = new Node();
            node = node->link[id[i]];
            node->indx.emplace_back(j);
        }
    }

    pair<int, int> rng(string &lft) {
        Node *node = root;
        for (auto i: lft) {
            i -= 'A';
            if (node->link[id[i]] == NULL) return {-1, -1};
            node = node->link[id[i]];
        }
        return {node->indx[0], node->indx.back()};
    }

    int get(string &rgt, int l, int r) {
        Node *node = root;
        for (auto &i: rgt) {
            i -= 'A';
            if (node->link[id[i]] == NULL) return 0;
            node = node->link[id[i]];
        }
        return lower_bound(node->indx.begin(), node->indx.end(), r + 1) -
               lower_bound(node->indx.begin(), node->indx.end(), l);
    }
};

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

    id[0] = 0;
    id['C' - 'A'] = 1;
    id['G' - 'A'] = 2;
    id['U' - 'A'] = 3;

    sort(s, s + n);
    Trie t1 = Trie(), t2 = Trie();
    for (int i = 0; i < n; ++i) {
        t1.insert(s[i], i);
    }

    for (int i = 0; i < n; ++i) {
        reverse(s[i].begin(), s[i].end());
        t2.insert(s[i], i);
    }
    while (m--) {
        string S, P;
        cin >> S >> P;
        reverse(P.begin(), P.end());
        pair<int, int> p = t1.rng(S);
        if (p.first == -1) {
            cout << 0;
        } else {
            cout << t2.get(P, p.first, p.second);
        }

        cout << '\n';
    }
}


signed main() {
    Pc_champs
    int t = 1;
    //cin >> t;
    while (t--) {
        ++idx;
        dowork();
        //cout << "\n";
    }
}

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