Submission #918872

#	Time	Username	Problem	Language	Result	Execution time	Memory
918872		Ska	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	189 ms	194384 KiB

selling_rna

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

const int N = 1e5 + 5;

int val(char c) {
    switch(c) {
        case 'A': return 0;
        case 'G': return 1;
        case 'C': return 2;
        default: return 3;
    }
}

struct Trie {
    struct Node {
        Node* child[4];
        int l, r;
        Node(): l(N), r(0) {
            fill(begin(child), end(child), nullptr);
        }
    };

    Node* root;
    Trie() {
        root = new Node();
    }

    void add(string &s, int id) {
        Node* p = root;
        for (auto &x: s) {
            int c = val(x);
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
    }

    pair<int, int> query(string &s) {
        pair<int, int> res = {0, N};
        Node* p = root;
        for (auto &x: s) {
            int c = val(x);
            if (p->child[c] == nullptr) return res;
            p = p->child[c];
            res.first = max(res.first, p->l);
            res.second = min(res.second, p->r);
        }
        return res;
    }
};

struct ReversedTrie {
    struct Node {
        Node* child[4];
        vector<int> ids;
        Node() {
            fill(begin(child), end(child), nullptr);
        }
    };

    Node* root;
    ReversedTrie() {
        root = new Node();
    }

    void add(string &s, int id) {
        Node* p = root;
        for (int i = s.size() - 1; i >= 0; --i) {
            int c = val(s[i]);
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
            p->ids.emplace_back(id);
        }
    }

    int query(string &s, pair<int, int> range) {
        Node* p = root;
        for (int i = s.size() - 1; i >= 0; --i) {
            int c = val(s[i]);
            if (p->child[c] == nullptr) return 0;
            p = p->child[c];
        }
        int l = lower_bound(p->ids.begin(), p->ids.end(), range.first) - p->ids.begin();
        int r = upper_bound(p->ids.begin(), p->ids.end(), range.second) - p->ids.begin() - 1;
        return r - l + 1;
    }
};

int n, q;
string a[N];
Trie trie1;
ReversedTrie trie2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        trie1.add(a[i], i);
        trie2.add(a[i], i);
    }

    while (q--) {
        string p, q;
        cin >> p >> q;
        auto range = trie1.query(p);
        if (!range.first) {
            cout << 0 << '\n';
            continue;
        }
        cout << trie2.query(q, range) << '\n';
    }
}

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