Submission #1267551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267551		dung3683833	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	313 ms	398840 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int trie[N][26];
int trier[N][26];
pair<int, int> d[N];
vector<int> dr[N];
string a[N];
int cnt = 0;
void add(string& s, int j) {
    int curr = 0;
    for (int i = 0; i < s.length(); i++) {
        if (!trie[curr][s[i]-'A']) {
            trie[curr][s[i]-'A'] = ++cnt;
        }
        curr = trie[curr][s[i]-'A'];
        d[curr].first = min(d[curr].first, j);
        d[curr].second = max(d[curr].second, j);
    }
}
pair<int, int> get(string& s) {
    int curr = 0;
    for (int i = 0; i < s.length(); i++) {
        if (!trie[curr][s[i] - 'A']) return {-1, -1};
        curr = trie[curr][s[i] - 'A'];
    }
    return d[curr];
}
int cntr = 0;
void addr(string& s, int j) {
    int curr = 0;
    for (int i = s.length()-1; i >= 0; i--) {
        if (!trier[curr][s[i]-'A']) {
            trier[curr][s[i]-'A'] = ++cntr;
        }
        curr = trier[curr][s[i]-'A'];
        dr[curr].push_back(j);
    }
}
int getr(string& s, pair<int, int> range) {
    int curr = 0;
    for (int i = s.length()-1; i >= 0; i--) {
        if (!trier[curr][s[i]-'A']) return 0;
        curr = trier[curr][s[i]-'A'];
    }
    return upper_bound(dr[curr].begin(), dr[curr].end(), range.second) - lower_bound(dr[curr].begin(), dr[curr].end(), range.first);
}
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    fill(d, d+N, make_pair(n+1, 0));
    for (int i = 1; i <= n; i++) {
        add(a[i], i);
        addr(a[i], i);
    }
    for (int i = 0; i < N; i++) {
        sort(dr[i].begin(), dr[i].end());
    }
    string p, q;
    while (m--) {
        cin >> p >> q;
        auto range = get(p);
        cout << getr(q, range) << '\n';
    }
    return 0;
}

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