Submission #1280845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280845		courte_.sanma	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	269 ms	210508 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int INF = 2000000000;

struct Node {
    int child[4];
    vector<int> ids; 
    int l, r; 
    Node() {
        memset(child, -1, sizeof(child));
        ids.clear();
        l = INF; r = 0;
    }
};

struct Trie {
    vector<Node> node;
    Trie() { node.emplace_back(); } // root = 0

    int new_node() {
        node.emplace_back();
        return (int)node.size() - 1;
    }

    void add(const string &s, int id, int type) {
        // update root to support empty query
        if (type == 2) node[0].ids.push_back(id);
        else { node[0].l = min(node[0].l, id); node[0].r = max(node[0].r, id); }

        int p = 0;
        for (char ch : s) {
            int x = ch - '0';
            if (x < 0 || x > 3) return; // defensive
            if (node[p].child[x] == -1) node[p].child[x] = new_node();
            p = node[p].child[x];
            if (type == 2) node[p].ids.push_back(id);
            else { node[p].l = min(node[p].l, id); node[p].r = max(node[p].r, id); }
        }
    }

    pii get_range(const string &s) {
        int p = 0;
        for (char ch : s) {
            int x = ch - '0';
            if (x < 0 || x > 3) return {-1,-1};
            int nxt = node[p].child[x];
            if (nxt == -1) return {-1,-1};
            p = nxt;
        }
        if (node[p].l > node[p].r) return {-1,-1};
        return {node[p].l, node[p].r};
    }

    vector<int> get_ids(const string &s) {
        int p = 0;
        for (char ch : s) {
            int x = ch - '0';
            if (x < 0 || x > 3) return {};
            int nxt = node[p].child[x];
            if (nxt == -1) return {};
            p = nxt;
        }
        return node[p].ids;
    }
};

void compress_string(string &s) {
    for (char &c : s) {
        if (c=='A' || c=='a') c='0';
        else if (c=='G' || c=='g') c='1';
        else if (c=='U' || c=='u') c='2';
        else if (c=='C' || c=='c') c='3';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    vector<string> orig(n+1);
    for (int i = 1; i <= n; ++i) cin >> orig[i];

    vector<pair<string,int>> arr;
    arr.reserve(n);
    for (int i = 1; i <= n; ++i) {
        string t = orig[i];
        compress_string(t);
        arr.emplace_back(t, i);
    }

    sort(arr.begin(), arr.end(), [](const pair<string,int>& a, const pair<string,int>& b){
        return a.first < b.first;
    });

    vector<string> s_sorted(n+1);
    vector<int> pos(n+1);
    for (int i = 0; i < n; ++i) {
        s_sorted[i+1] = arr[i].first;
        pos[arr[i].second] = i+1;
    }

    Trie pre, suf;
    for (int i = 1; i <= n; ++i) {
        pre.add(s_sorted[i], i, 1);
    }
    for (int orig_idx = 1; orig_idx <= n; ++orig_idx) {
        string t = arr[ pos[orig_idx] - 1 ].first; 
    }
    for (int i = 1; i <= n; ++i) {
        string t = orig[i];
        compress_string(t);
        reverse(t.begin(), t.end());
        suf.add(t, pos[i], 2); 
    }

    for (auto &nd : suf.node) {
        if (!nd.ids.empty()) sort(nd.ids.begin(), nd.ids.end());
    }

    while (q--) {
        string P, Q;
        cin >> P >> Q;
        compress_string(P);
        compress_string(Q);
        pii range = pre.get_range(P);
        if (range.first == -1) { cout << 0 << '\n'; continue; }

        reverse(Q.begin(), Q.end());
        vector<int> vec = suf.get_ids(Q);
        if (vec.empty()) { cout << 0 << '\n'; continue; }

        int L = lower_bound(vec.begin(), vec.end(), range.first) - vec.begin();
        int R = upper_bound(vec.begin(), vec.end(), range.second) - vec.begin();
        cout << (R - L) << '\n';
    }

    return 0;
}

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