Submission #1099501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099501		ShadowShark	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	101 ms	68956 KiB

selling_rna

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

const int maxN = 1e5 + 5, maxC = 2e6 + 5;
int convert[26], ans[maxN]; string S[maxN];

namespace pref {
    int to[maxC][4], mn[maxC], mx[maxC], currNode = 0;

    void add_string(string s, int id) {
        int u = 0;
        for (auto ch: s) {
            int x = ch - 'A'; x = convert[x];
            if (!to[u][x]) to[u][x] = ++currNode;
            u = to[u][x];
            mx[u] = id; if (!mn[u]) mn[u] = id;
        }
    }

    pair <int, int> get(string s) {
        int u = 0;
        for (auto ch: s) {
            int x = ch - 'A'; x = convert[x];
            if (!to[u][x]) return {-1, -1};
            u = to[u][x];
        }
        return {mn[u], mx[u]};
    }
}

namespace suff {
    int to[maxC][4], cnt[maxC], currNode = 0;

    void add_string(string S) {
        int u = 0;
        for (int i = S.size() - 1; i >= 0; i--) {
            int x = S[i] - 'A'; x = convert[x];
            if (!to[u][x]) to[u][x] = ++currNode;
            u = to[u][x]; cnt[u]++;
        }
    }

    void delete_string(string S) {
        int u = 0;
        for (int i = S.size() - 1; i >= 0; i--) {
            int x = S[i] - 'A'; x = convert[x];
            u = to[u][x]; cnt[u]--;
        }
    }

    int get(string S) {
        int u = 0;
        for (int i = S.size() - 1; i >= 0; i--) {
            int x = S[i] - 'A'; x = convert[x];
            if (!to[u][x]) return 0;
            u = to[u][x];
        }
        return cnt[u];
    }
}

struct event {
    string P, Q;
    int id;

    bool operator < (const event& rhs) const {
        return P < rhs.P;
    }

} query[maxN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    convert[0] = 0; convert[2] = 1; convert[6] = 2; convert[20] = 3;

    int n, TiaChem;
    cin >> n >> TiaChem;

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

    sort(S + 1, S + n + 1);
    for (int i = 1; i <= n; i++) {
        pref::add_string(S[i], i);
        //cout << i << ' ' << S[i] << '\n';
    }

    for (int i = 1; i <= TiaChem; i++) {
        cin >> query[i].P >> query[i].Q;
        query[i].id = i;
    }

    sort(query + 1, query + TiaChem + 1);

    //cout << '\n';

    int L = 1, R = 0;
    for (int i = 1; i <= TiaChem; i++) {
        pair<int, int> range = pref::get(query[i].P);

        //cout << query[i].P << ' ' << query[i].Q << ' ' << range.first << ' ' << range.second << '\n';

        if (range.first == -1) {
            ans[query[i].id] = 0;
            continue;
        }

        while (R < range.second) suff::add_string(S[++R]);
        while (R > range.second) suff::delete_string(S[R--]);
        while (L < range.first) suff::delete_string(S[L++]);

        //cout << L << ' ' << R << '\n';

        ans[query[i].id] = suff::get(query[i].Q);
    }

    for (int i = 1; i <= TiaChem; i++)
        cout << ans[i] << '\n';

    return 0;
}

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