Submission #1279951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279951		tanphat29	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	219 ms	190996 KiB

selling_rna

#include <bits/stdc++.h>
#define name "test"
#define ll long long
#define fi first
#define se second
#define el '\n'
#define pback push_back
#define popback pop_back
#define pii pair <int, int>
#define plli pair <ll, int>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

const int N = 1e5 + 5;
const int MASK = (1 << 17);
const int base = 31;
const ll MOD = 1e9 + 7;

int n, m;
string s[N];

int cal(char c){
    if(c == 'A') return 0;
    if(c == 'U') return 1;
    if(c == 'G') return 2;
    return 3;
}

struct trie1 {
    trie1 *child[4];
    int l, r;
    trie1() {
        FOR(i, 0, 3) child[i] = NULL, l = 1e9, r = 0;
    }
};

struct trie2 {
    trie2 *child[4];
    vector <int> id;
    trie2() {
        FOR(i, 0, 3) child[i] = NULL;
    }
};

trie1 *root1;
trie2 *root2;

void add_pre(string s, int id) {
    trie1 *p = root1;
    FOR(i, 0, s.size() - 1) {
        int x = cal(s[i]);
        if (p -> child[x] == NULL) p -> child[x] = new trie1();
        p = p -> child[x];
        p -> l = min(p -> l, id);
        p -> r = max(p -> r, id);
    }
}

void add_suff(string s, int pos) {
    reverse(s.begin(), s.end());
    trie2 *p = root2;
    FOR(i, 0, s.size() - 1) {
        int x = cal(s[i]);
        if (p -> child[x] == NULL) p -> child[x] = new trie2();
        p = p -> child[x];
        p -> id.pback(pos);
    }
}

pii get_pre(string s) {
    trie1 *p = root1;
    FOR(i, 0, s.size() - 1) {
        int x = cal(s[i]);
        if (p -> child[x] == NULL) return {-1, -1};
        p = p -> child[x];
    }
    return {p -> l, p -> r};
}

int get_suf(string s, pii d) {
    int l = d.fi, r = d.se;
    if (l == -1) return 0;
    trie2 *p = root2;
    FOR(i, 0, s.size() - 1) {
        int x = cal(s[i]);
        if (p -> child[x] == NULL) return 0;
        p = p -> child[x];
    }
    vector <int> &b = p -> id;
    return upper_bound(b.begin(), b.end(), r) - lower_bound(b.begin(), b.end(), l);
}

void dfs(trie2 *p) {
    if (p == NULL) return;
    sort(p -> id.begin(), p -> id.end());
    FOR(i, 0, 3) if (p -> child[i]) dfs(p -> child[i]);
}

void input() {
    cin >> n >> m;
    root1 = new trie1();
    root2 = new trie2();
    FOR(i, 1, n) cin >> s[i];
    sort(s + 1, s + n + 1);
    FOR(i, 1, n) {
        add_pre(s[i], i);
        add_suff(s[i], i);
    }
    dfs(root2);
    while (m--) {
        string x, y;
        cin >> x >> y;
        reverse(y.begin(), y.end());
        cout << get_suf(y, get_pre(x)) << el;
    }
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);
    //
    input();
    //cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
    return 0;
}

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