Submission #1002436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002436		nmts	Selling RNA Strands (JOI16_selling_rna)	C++17	35 / 100	1577 ms	267748 KiB

selling_rna

#include <bits/stdc++.h>

#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
#define fi first
#define se second
#define endl '\n'
#define int long long

const int maxn = 1e6 + 6;
const int INF = 1e9;

using namespace std;

int n, m;
string s[maxn];

int get_val(char ch) {
    return (ch == 'A' ? 1 : ch == 'G' ? 2 : ch == 'C' ? 3 : 4);
}

struct Trie {
    struct Node {
        Node* child[5];
        int l, r;
        int exits;
        Node() {
            for (int i = 1; i <= 4; ++i) child[i] = NULL;
            l = INF;
            r = -INF;
            exits = 0;
        }
    };

    Node* root;

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

    void add(string s, int id) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) p->child[val] = new Node;
            p = p->child[val];
            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
        p->exits++;
    }

    pii get_range(string s) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) return {-1, -1};
            p = p->child[val];
        }
        return {p->l, p->r};
    }
};

struct RTrie {
    struct Node {
        Node* child[5];
        vector<int> exits;
        Node() {
            for (int i = 1; i <= 4; ++i) child[i] = NULL;
            exits.clear();
        }
    };

    Node* root;

    RTrie() {
        root = new Node;
    };

    void add(string s, int id) {
        Node* p = root;
        for (char c : s) {
            p->exits.push_back(id);
            int val = get_val(c);
            if (p->child[val] == NULL) p->child[val] = new Node;
            p = p->child[val];
        }
        p->exits.push_back(id);
    }

    int get_ans(string s, int u, int v) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) return 0;
            p = p->child[val];
        }

        sort(p->exits.begin(), p->exits.end());
        int l = lower_bound(p->exits.begin(), p->exits.end(), u) - p->exits.begin();
        int r = upper_bound(p->exits.begin(), p->exits.end(), v) - p->exits.begin() - 1;

        return r - l + 1;
    }
};

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) cin >> s[i];

    sort(s + 1, s + n + 1);

    Trie tr;
    RTrie Rtr;
    for (int i = 1; i <= n; ++i) {
        tr.add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        Rtr.add(s[i], i);
    }

    while (m--) {
        string a, b;
        cin >> a >> b;
        pii it = tr.get_range(a);
        reverse(b.begin(), b.end());
        if (it.fi == -1) cout << 0 << '\n';
        else cout << Rtr.get_ans(b, it.fi, it.se) << '\n';
    }
}

int32_t main() {
    faster;
    solve();
    return 0;
}

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