oj.uz

Submission #784870

# Submission time Handle Problem Language Result Execution time Memory
784870 2023-07-16T16:04:04 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 411 ms 189880 KB 
#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

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 58 ms 125420 KB Output is correct
2 Correct 59 ms 125412 KB Output is correct
3 Correct 58 ms 125440 KB Output is correct
4 Correct 58 ms 125500 KB Output is correct
5 Correct 59 ms 125448 KB Output is correct
6 Correct 59 ms 125408 KB Output is correct
7 Correct 60 ms 125528 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 189880 KB Output is correct
2 Correct 294 ms 186872 KB Output is correct
3 Correct 242 ms 139832 KB Output is correct
4 Correct 231 ms 139256 KB Output is correct
5 Correct 229 ms 165652 KB Output is correct
6 Correct 241 ms 166408 KB Output is correct
7 Correct 285 ms 136048 KB Output is correct
8 Correct 384 ms 156236 KB Output is correct
9 Correct 362 ms 152324 KB Output is correct
10 Correct 272 ms 151948 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 128200 KB Output is correct
2 Correct 115 ms 127352 KB Output is correct
3 Correct 130 ms 127704 KB Output is correct
4 Correct 119 ms 127352 KB Output is correct
5 Correct 121 ms 127348 KB Output is correct
6 Correct 129 ms 127680 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 125420 KB Output is correct
2 Correct 59 ms 125412 KB Output is correct
3 Correct 58 ms 125440 KB Output is correct
4 Correct 58 ms 125500 KB Output is correct
5 Correct 59 ms 125448 KB Output is correct
6 Correct 59 ms 125408 KB Output is correct
7 Correct 60 ms 125528 KB Output is correct
8 Correct 295 ms 189880 KB Output is correct
9 Correct 294 ms 186872 KB Output is correct
10 Correct 242 ms 139832 KB Output is correct
11 Correct 231 ms 139256 KB Output is correct
12 Correct 229 ms 165652 KB Output is correct
13 Correct 241 ms 166408 KB Output is correct
14 Correct 285 ms 136048 KB Output is correct
15 Correct 384 ms 156236 KB Output is correct
16 Correct 362 ms 152324 KB Output is correct
17 Correct 272 ms 151948 KB Output is correct
18 Correct 142 ms 128200 KB Output is correct
19 Correct 115 ms 127352 KB Output is correct
20 Correct 130 ms 127704 KB Output is correct
21 Correct 119 ms 127352 KB Output is correct
22 Correct 121 ms 127348 KB Output is correct
23 Correct 129 ms 127680 KB Output is correct
24 Correct 332 ms 179336 KB Output is correct
25 Correct 392 ms 179496 KB Output is correct
26 Correct 316 ms 178648 KB Output is correct
27 Correct 264 ms 139124 KB Output is correct
28 Correct 411 ms 147524 KB Output is correct
29 Correct 330 ms 134332 KB Output is correct