Submission #784869

#	Time	Username	Problem	Language	Result	Execution time	Memory
784869		Antonn_114	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	416 ms	191712 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
const int sz = 2e6+5;
struct Prefix{
    int nxt[4];
    int Min = sz, Max = 0;
    Prefix(){
        nxt[0] = nxt[1] = nxt[2] = nxt[3] = -1;
    }
};
struct Suffix{
    int nxt[4];
    vector<int> indices;
    Suffix(){
        nxt[0] = nxt[1] = nxt[2] = nxt[3] = -1;
    }
};
Prefix prefix[sz];
Suffix suffix[sz];
int t_p = 1, t_q = 1;
unordered_map<char, int> idx = {
    {'A', 0},
    {'C', 1},
    {'G', 2},
    {'U', 3}
};

void add_str(const string &s, int idc){
    prefix[0].Min = min(prefix[0].Min, idc);
    prefix[0].Max = max(prefix[0].Max, idc);
    suffix[0].indices.push_back(idc);
    int curr_idx = 0;
    for (const char &ch : s){
        if (prefix[curr_idx].nxt[idx[ch]] == -1){
            prefix[curr_idx].nxt[idx[ch]] = t_p++;
        }
        curr_idx = prefix[curr_idx].nxt[idx[ch]];
        prefix[curr_idx].Min = min(prefix[curr_idx].Min, idc);
        prefix[curr_idx].Max = max(prefix[curr_idx].Max, idc);
    }
    curr_idx = 0;
    for (int i = s.size() - 1; i>=0;i--){
        const char &ch = s[i];
        if (suffix[curr_idx].nxt[idx[ch]] == -1){
            suffix[curr_idx].nxt[idx[ch]] = t_q++;
        }
        curr_idx = suffix[curr_idx].nxt[idx[ch]];
        suffix[curr_idx].indices.push_back(idc);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> ss(n);
    for (int i = 0; i < n; i++){
        cin >> ss[i];
    }
    sort(ss.begin(), ss.end());
    for (int i = 0; i < n; i++){
        add_str(ss[i], i);
    }
    for (int i = 0; i < m; i++){
        string p, q;
        cin >> p >> q;
        int MinRange, MaxRange;
        int curr_idx = 0;
        bool ok = true;
        for (int j = 0; j < p.size(); j++){
            if (prefix[curr_idx].nxt[idx[p[j]]] == -1){
                ok = false;
                break;
            }
            curr_idx = prefix[curr_idx].nxt[idx[p[j]]];
        }
        if (!ok){
            cout << 0 << endl;
            continue;
        }
        MinRange = prefix[curr_idx].Min;
        MaxRange = prefix[curr_idx].Max; 
        curr_idx = 0;
        for (int j = q.size() - 1; j >= 0; j--){
            if (suffix[curr_idx].nxt[idx[q[j]]] == -1){
                ok = false;
                break;
            }
            curr_idx = suffix[curr_idx].nxt[idx[q[j]]];
        }
        if (!ok){
            cout << 0 << endl;
            continue;
        }
        vector<int> &a = suffix[curr_idx].indices;
        auto it = lower_bound(a.begin(), a.end(), MinRange);
        auto jt = upper_bound(a.begin(), a.end(), MaxRange);
        int res = jt - it;
        cout << res << endl;
    }
	return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 0; j < p.size(); j++){
      |                         ~~^~~~~~~~~~

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