oj.uz

Submission #784867

# Submission time Handle Problem Language Result Execution time Memory
784867 2023-07-16T16:02:33 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 225 ms 198876 KB 
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e6+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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62792 KB Output is correct
2 Correct 33 ms 62900 KB Output is correct
3 Correct 33 ms 62888 KB Output is correct
4 Correct 32 ms 62804 KB Output is correct
5 Correct 33 ms 62896 KB Output is correct
6 Correct 34 ms 62796 KB Output is correct
7 Correct 33 ms 62932 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 225 ms 198876 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 65532 KB Output is correct
2 Correct 87 ms 64972 KB Output is correct
3 Correct 124 ms 65384 KB Output is correct
4 Correct 105 ms 65232 KB Output is correct
5 Correct 88 ms 64964 KB Output is correct
6 Correct 103 ms 65460 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62792 KB Output is correct
2 Correct 33 ms 62900 KB Output is correct
3 Correct 33 ms 62888 KB Output is correct
4 Correct 32 ms 62804 KB Output is correct
5 Correct 33 ms 62896 KB Output is correct
6 Correct 34 ms 62796 KB Output is correct
7 Correct 33 ms 62932 KB Output is correct
8 Runtime error 225 ms 198876 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -