Submission #601814

#	Time	Username	Problem	Language	Result	Execution time	Memory
601814		elkernos	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	289 ms	191504 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

struct T {
    int nxt[4] = {-1, -1, -1, -1};
    vector<int> id;
};

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

struct tree {
    vector<T> trie;
    tree() { trie.emplace_back(); }
    void insert(string &s, int i)
    {
        int v = 0;
        for(char x : s) {
            int id = mapuj(x);
            if(trie[v].nxt[id] == -1) {
                trie[v].nxt[id] = (int)trie.size();
                trie.emplace_back();
            }
            trie[v].id.emplace_back(i);
            v = trie[v].nxt[id];
        }
        trie[v].id.emplace_back(i);
    }
    int search(string &s)
    {
        int v = 0;
        for(char x : s) {
            int id = mapuj(x);
            if(trie[v].nxt[id] == -1) {
                return -1;
            }
            v = trie[v].nxt[id];
        }
        return v;
    }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;
    vector<string> s(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    sort(1 + s.begin(), s.end());
    tree trie, trierev;
    for(int i = 1; i <= n; ++i) {
        trie.insert(s[i], i);
        reverse(s[i].begin(), s[i].end());
        trierev.insert(s[i], i);
    }
    for(int i = 1; i <= q; i++) {
        string pre, suf;
        cin >> pre >> suf;
        int one = trie.search(pre);
        reverse(suf.begin(), suf.end());
        int two = trierev.search(suf);
        if(one == -1 || two == -1) {
            cout << 0 << '\n';
            continue;
        }
        vector<int> &wek1 = trie.trie[one].id;
        vector<int> &wek2 = trierev.trie[two].id;
        int lo = wek1.front(), hi = wek1.back();
        auto it1 = lower_bound(wek2.begin(), wek2.end(), lo);
        auto it2 = upper_bound(wek2.begin(), wek2.end(), hi);
        if(it1 == wek2.end() || hi < *it1) {
            cout << 0 << '\n';
            continue;
        }
        cout << distance(it1, it2) << '\n';
    }
}

Compilation message (stderr)

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

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