Submission #1282813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282813		dhuyyyy	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	225 ms	238628 KiB

selling_rna

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 2e6+5;
const int MOD = 1e9+7;

int n, q, timer = 0, timer1 = 0;

int pre[N][4], suf[N][4];

vector <int> bitpre[N], bitsuf[N];

string s[N];
string s1, s2;

int get(char c){
    if (c == 'A') return 0;
    if (c == 'G') return 1;
    if (c == 'C') return 2;
    return 3;
}
void addpre(string s,int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!pre[node][val]) pre[node][val] = ++timer;
        node = pre[node][val];
        bitpre[node].push_back(i);
    }
}
ii getpre(string s){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!pre[node][val]) return {-1,-1};
        node = pre[node][val];
    }
    return {bitpre[node][0],bitpre[node][(int)bitpre[node].size() - 1]};
}
void addsuf(string s,int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!suf[node][val]) suf[node][val] = ++timer1;
        node = suf[node][val];
        bitsuf[node].push_back(i);
    }
}
int getsuf(string s,int l,int r){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!suf[node][val]) return 0;
        node = suf[node][val];
    }
    int lo = lower_bound(bitsuf[node].begin(),bitsuf[node].end(),l) - bitsuf[node].begin();
    int hi = upper_bound(bitsuf[node].begin(),bitsuf[node].end(),r) - bitsuf[node].begin();
    return hi - lo;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s+1,s+1+n);
    for (int i = 1; i <= n; i++){
        addpre(s[i],i);
        reverse(s[i].begin(),s[i].end());
        addsuf(s[i],i);
    }
    while (q--){
        cin >> s1 >> s2;
        ii res = getpre(s1);
        if (res.fi == -1) cout << 0 << '\n';
        else{
            reverse(s2.begin(),s2.end());
            cout << getsuf(s2,res.fi,res.se) << '\n';
        }

    }
    return 0;
}

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