Submission #1237753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237753		mohamed	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	1063 ms	698324 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define el endl
#define pb push_back
#define all(x) begin(x), end(x)
using namespace std;
const int modd = 1e9 + 7;

void MO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct Node {
    unordered_map<char, int> nxt;
    int isEnd = 0, sz = 0;

    int &operator[](char x) {
        return nxt[x];
    }
};

struct Trie {
    vector<Node> tr;
    int M = 'Z'+4;
    vector<ll> l, r; // start & end for each id
    vector<vector<ll>> b;

    int newNode() {
        tr.emplace_back();
        l.emplace_back();
        r.emplace_back();
        b.emplace_back();
        return tr.size() - 1;
    }

    Trie() {
        tr.clear();
        newNode();
    }

    int id = 0;

    void insert(string &s) {
        id++;
        int u = 0;
        for (char c: s) {
            if (!tr[u][c]) {
                tr[u][c] = newNode();
                l[tr[u][c]] = id;
                r[tr[u][c]] = id;
            }
            tr[u].sz++;
            u = tr[u][c];
            r[u] = id;
            b[u].push_back(id);
        }
        tr[u].sz++;
        tr[u].isEnd++;
        r[u] = id;
    }

    pair<ll, ll> startWith(string &s) {
        int u = 0;
        for (char c: s) {
            if (!tr[u][c]) return {-1, -1};
            u = tr[u][c];
        }
        return {l[u], r[u]};
    }

    ll startWithSuf(string &s) {
        int u = 0;
        for (char c: s) {
            if (!tr[u][c]) return -1;
            u = tr[u][c];
        }
        return u;
    }
};

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<string> data;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        data.pb(s);
    }
    sort(all(data));

    Trie trprefix;
    Trie trsuffix;
//    string ee = "hel",ee1 ="hen",e = "he";
//    trprefix.insert(ee);
//    trprefix.insert(ee1);
//    cout << trprefix.startWith(e).second << el;
    for (int i = 0; i < n; i++) {
        trprefix.insert(data[i]);
        string rev = data[i];
        reverse(all(rev));
        trsuffix.insert(rev);
    }

    // Sort all b vectors for binary search
    for (int i = 0; i < trsuffix.tr.size(); i++) {
        sort(all(trsuffix.b[i]));
    }


    for (ll i = 0; i < q; i++) {
        string s, t;
        cin >> s >> t;
        reverse(all(t));
        auto [l, r] = trprefix.startWith(s);
       // cout << l << " " << r << el;
        if (l == -1) {
            cout << 0 << el;
            continue;
        }

        int temp = trsuffix.startWithSuf(t);
        if (temp == -1) {
            cout << 0 << el;
            continue;
        }

        // Find count of elements in trsuffix.b[temp] that are in range [l, r]
        auto &vec = trsuffix.b[temp];
        int left_idx = lower_bound(all(vec), l) - vec.begin();
        int right_idx = upper_bound(all(vec), r) - vec.begin();

        cout << right_idx - left_idx << el;
    }
}

signed main() {
    MO();
    int t = 1;
    while (t--) {
        solve();
    }
}

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