Submission #1165711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165711		nguyn	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	209 ms	254928 KiB

selling_rna

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 1e5 + 5;
const int M = 2e6 + 5;


int getId(char c) {
    if (c == 'A') return 0;
    if (c == 'U') return 1;
    if (c == 'G') return 2;
    if (c == 'C') return 3;
}

struct Trie {
    struct Node{
        int child[4];
        int l, r;
        vector<int> vec;
        Node() {
            memset(child, -1, sizeof(child));
            r = -1;
            l = 1e9;
        }
    };

    Trie() {}

    Node nodes[M];
    int cur = 0;

    void add(const string &s, int id) {
        int pos = 0;
        for (auto it : s) {
            int c = getId(it);
            if (nodes[pos].child[c] == -1) {
                cur++;
                nodes[pos].child[c] = cur; 
                nodes[cur] = Node();
            }
            pos = nodes[pos].child[c];
            nodes[pos].l = min(nodes[pos].l, id);
            nodes[pos].r = max(nodes[pos].r, id);
        }
    }
    pii get(string &p) {
        int pos = 0;
        for (auto it : p) {
            int c = getId(it);
            if (nodes[pos].child[c] == -1) {
                return {1e9, -1};
            }
            pos = nodes[pos].child[c];
        }
        return {nodes[pos].l, nodes[pos].r};
    }

    void addSuffix(const string &s, int id) {
        int pos = 0;
        for (auto it : s) {
            int c = getId(it);
            if (nodes[pos].child[c] == -1) {
                cur++;
                nodes[pos].child[c] = cur; 
                nodes[cur] = Node();
            }
            pos = nodes[pos].child[c];
            // cout << pos << ' ' << it << '\n';
            nodes[pos].vec.pb(id);
        }
    }

    int query(const string &q, int l, int r) {
        int pos = 0;
        for (auto it : q) {
            int c = getId(it);
            if (nodes[pos].child[c] == -1) {
                return 0;
            }
            pos = nodes[pos].child[c];
        }
        // for (auto it : nodes[pos].vec) {
        //     cout << it << " ";
        // }cout << endl;
        int x = upper_bound(nodes[pos].vec.begin(), nodes[pos].vec.end(), r) - lower_bound(nodes[pos].vec.begin(), nodes[pos].vec.end(), l);
        return x;
    }

};


Trie chim;
Trie tri;
int n, m;
string s[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) {
        chim.add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        tri.addSuffix(s[i], i);
    }
    for (int i = 1; i <= m; i++) {
        string p, q;
        cin >> p >> q;
        pii x = chim.get(p);
        if (x.F == 1000000000) {
            cout << 0 << '\n';
            continue;
        }
        reverse(q.begin(), q.end());
        cout << tri.query(q, x.F, x.S) << '\n';
    }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int getId(char)':
selling_rna.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
   19 | }
      | ^

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