Submission #1279961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279961		nguyenphucanhkhoi	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	245 ms	229924 KiB

selling_rna

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

struct Node {
    Node* child[4];
    vector<int> pre;
    bool exist = false;
    Node() { for (int i = 0; i < 4; ++i) child[i] = nullptr; }
};

struct Trie {
    Node* root;
    Trie() { root = new Node(); }
    // s must consist of letters 'A'..'D' only (we use 0..3)
    void add(const string &s, int idx) {
        Node* p = root;
        p->pre.push_back(idx);
        for (char ch : s) {
            int c = ch - 'A';
            if (c < 0 || c > 3) return; // defensive (shouldn't happen)
            if (!p->child[c]) p->child[c] = new Node();
            p = p->child[c];
            p->pre.push_back(idx);
        }
        p->exist = true;
    }
    // sort pre vectors in the whole trie
    void sort_all(Node* p = nullptr) {
        if (p == nullptr) p = root;
        sort(p->pre.begin(), p->pre.end());
        for (int i = 0; i < 4; ++i)
            if (p->child[i]) sort_all(p->child[i]);
    }
    // find node representing string s (or nullptr)
    Node* find_node(const string &s) {
        Node* p = root;
        for (char ch : s) {
            int c = ch - 'A';
            if (c < 0 || c > 3) return nullptr;
            if (!p->child[c]) return nullptr;
            p = p->child[c];
        }
        return p;
    }
};

// map AGCU -> A,B,C,D so letters are 'A'..'D'
string trans(const string &inp) {
    string out;
    out.reserve(inp.size());
    for (char ch : inp) {
        if (ch == 'A') out.push_back('A');
        else if (ch == 'G') out.push_back('B');
        else if (ch == 'C') out.push_back('C');
        else if (ch == 'U') out.push_back('D');
        else {
            // if there are lowercase or T etc, you may want to handle or convert
            out.push_back(ch); // defensive
        }
    }
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // optional file redir for local:
    // if (fopen("DELSEQ.INP", "r")) { freopen("DELSEQ.INP", "r", stdin); freopen("DELSEQ.OUT", "w", stdout); }

    int n, m;
    if (!(cin >> n >> m)) return 0;
    Trie tPref, tSuf; // tPref -> prefixes; tSuf -> reversed strings (to handle suffixes)
    vector<string> arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        string tmp; cin >> tmp;
        string tr = trans(tmp);
        arr[i] = tr;
        // add to prefix trie with index i
        tPref.add(tr, i);
        // add reversed string to suffix trie with index i
        reverse(tr.begin(), tr.end());
        tSuf.add(tr, i);
    }

    // sort all pre vectors so lower_bound/upper_bound work
    tPref.sort_all();
    tSuf.sort_all();

    while (m--) {
        string p, q; cin >> p >> q;
        p = trans(p);
        q = trans(q);

        // find prefix node in tPref
        Node* nodeP = tPref.find_node(p);
        if (nodeP == nullptr || nodeP->pre.empty()) {
            cout << 0 << '\n';
            continue;
        }
        int L = nodeP->pre.front(); // minimum original index with prefix p
        int R = nodeP->pre.back();  // maximum original index with prefix p

        // find suffix node in reversed trie (we must reverse q)
        reverse(q.begin(), q.end());
        Node* nodeQ = tSuf.find_node(q);
        if (nodeQ == nullptr || nodeQ->pre.empty()) {
            cout << 0 << '\n';
            continue;
        }

        // count how many indices in nodeQ->pre fall into [L, R]
        auto &vec = nodeQ->pre;
        int lp = int(lower_bound(vec.begin(), vec.end(), L) - vec.begin());
        int rp = int(upper_bound(vec.begin(), vec.end(), R) - vec.begin());
        cout << (rp - lp) << '\n';
    }
    return 0;
}

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