Submission #1279342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279342		MinhKien	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	173 ms	200140 KiB

selling_rna

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
const int M = 2e6 + 10;
const int C = 4;

int n, m, x, y;
string s[N], pre, suf;

struct Trie {
    struct node {
        int child[C], cnt;
        pair <int, int> rg;

        node () {
            rg = pair <int, int>(-1, 0);
            fill_n(child, C, -1);
        }
    } nd[M];

    int root, cnt;
    Trie () {
        root = cnt = 0;
    }

    void NewNode(int u, int c) {
        nd[u].child[c] = ++cnt;
    }

    void add(int id) {
        int cur = root, kk = s[id].size();
        for (int i = 0; i < kk; ++i) {
            int c = s[id][i] - 'A';
            if (nd[cur].child[c] == -1) NewNode(cur, c);
            cur = nd[cur].child[c];
            if (nd[cur].rg.first == -1) nd[cur].rg.first = id;
            nd[cur].rg.second = id;
        }
    }

    pair <int, int> get() {
        int cur = 0;
        for (int i = 0; i < x; ++i) {
            int c = pre[i] - 'A';
            if (nd[cur].child[c] == -1) return pair <int, int>(0, 0);
            cur = nd[cur].child[c];
        }
        return nd[cur].rg;
    }
} T;

struct RevTrie {
    struct node {
        int child[4];
        vector <int> ids;

        node () {
            fill_n(child, 4, -1);
            ids.clear();
        }
    } nd[M];

    int root, cnt;
    RevTrie() {
        root = cnt = 0;
    }

    void NewNode(int u, int c) {
        nd[u].child[c] = ++cnt;
    }

    void add(int id) {
        reverse(s[id].begin(), s[id].end());
        int cur = root;
        for (int i = 0; i < (int)s[id].size(); ++i) {
            int c = s[id][i] - 'A';
            if (nd[cur].child[c] == -1) NewNode(cur, c);
            cur = nd[cur].child[c];
            nd[cur].ids.push_back(id);
        }
    }

    int get(pair <int, int> rg) {
        reverse(suf.begin(), suf.end());
        int cur = root;
        for (int i = 0; i < y; ++i) {
            int c = suf[i] - 'A';
            if (nd[cur].child[c] == -1) return 0;
            cur = nd[cur].child[c];
        }

        int l = lower_bound(nd[cur].ids.begin(), nd[cur].ids.end(), rg.first) - nd[cur].ids.begin();
        int r = lower_bound(nd[cur].ids.begin(), nd[cur].ids.end(), rg.second + 1) - nd[cur].ids.begin() - 1;

        return r - l + 1;
    }
} RT;

void change(string &kk) {
    for (int i = 0; i < (int)kk.size(); ++i) {
        if (kk[i] == 'U') kk[i] = 'B';
        else if (kk[i] == 'G') kk[i] = 'D';
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        change(s[i]);
    }
    sort(s + 1, s + n + 1);

    for (int i = 1; i <= n; ++i) {
        T.add(i);
        RT.add(i);
    }

    while (m--) {
        cin >> pre >> suf;
        x = pre.size(); y = suf.size();
        change(pre); change(suf);
        cout << RT.get(T.get()) << "\n";
    }

    return 0;
}

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