Submission #1199219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199219		qrn	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	333 ms	195452 KiB

selling_rna

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 41;
const intt inf = 1e18;
const intt mxN = 5005;
const intt L = 21;

intt f(char c) {
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    return 3;
}

struct trie {
    trie *kids[4];
    intt mn, mx;
    trie () {
        for(intt i = 0; i < 4; i++) {
            kids[i] = nullptr;
        }
        mn = inf, mx = -inf;
    }
};

void add(trie *&root, string s, intt idx) {
    trie *node = root;
    intt N = (intt)s.size();
    for(intt i = 0; i < N; i++) {
        intt num = f(s[i]);
        if(node->kids[num] == nullptr) {
            node->kids[num] = new trie();
        }
        node = node->kids[num];
        node->mn = min(node->mn, idx);
        node->mx = max(node->mx, idx);
    }
}

//-------------------------------------------------------------------------------------------------------------------------------------------------------

struct rtrie{
    rtrie *kids[4];
    vector<intt> data;
    rtrie () {
        for(intt i = 0; i < 4; i++) {
            kids[i] = nullptr;
        }
        data.clear();
    }
};

void radd(rtrie *& root, string s, intt idx) {
    rtrie *node = root;
    intt N = (intt)s.size();
    for(intt i = 0; i < N; i++) {
        intt num = f(s[i]);
        if(node->kids[num] == nullptr) {
            node->kids[num] = new rtrie();
        }
        node = node->kids[num];
        node->data.pb(idx);
    }
}


void solve() {
    intt N, M;
    cin >> N >> M;
    trie *root = new trie();
    rtrie *rroot = new rtrie();
    vector<string> words;
    for(intt i = 0; i < N; i++) {
        string s;
        cin >> s;
        words.pb(s);
    }
    sort(ALL(words));
    for(intt i = 0; i < N; i++) {
        string s = words[i];
        add(root, s, i);
        reverse(ALL(s));
        radd(rroot, s, i);
    }

    for(intt i = 0; i < M; i++) {
        string pre, suf;
        cin >> pre >> suf;
        reverse(ALL(suf));

        trie *node = root;
        for(intt j = 0; j < pre.size(); j++) {
            intt num = f(pre[j]);
            if(node->kids[num] != nullptr) {
                node = node->kids[num];
            } else {
                node = nullptr;
                break;
            }
        }
        if(node == nullptr) {
            cout << 0 << endl;
            continue;
        }

        rtrie *rnode = rroot;
        for(intt j = 0; j < suf.size(); j++) {
            intt num = f(suf[j]);
            if(rnode->kids[num] != nullptr) {
                rnode = rnode->kids[num];
            } else {
                rnode = nullptr;
                break;
            }
        }
        if(rnode == nullptr) {
            cout << 0 << endl;
            continue;
        }
        vector<intt> v = rnode->data;
        cout << upper_bound(ALL(v), node->mx) - lower_bound(ALL(v), node->mn) << endl;
        // cout << node->mn << " " << node->mx << " :::: ";
        // for(intt j : v) cout << j << " ";
        // cout << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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