oj.uz

Submission #784869

# Submission time Handle Problem Language Result Execution time Memory
784869 2023-07-16T16:03:46 Z Antonn_114 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 416 ms 191712 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 65 ms 125512 KB Output is correct
2 Correct 60 ms 125448 KB Output is correct
3 Correct 59 ms 125516 KB Output is correct
4 Correct 58 ms 125512 KB Output is correct
5 Correct 59 ms 125424 KB Output is correct
6 Correct 59 ms 125528 KB Output is correct
7 Correct 58 ms 125488 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 191712 KB Output is correct
2 Correct 310 ms 190796 KB Output is correct
3 Correct 238 ms 143636 KB Output is correct
4 Correct 233 ms 143252 KB Output is correct
5 Correct 230 ms 168128 KB Output is correct
6 Correct 237 ms 168780 KB Output is correct
7 Correct 284 ms 141476 KB Output is correct
8 Correct 383 ms 162180 KB Output is correct
9 Correct 370 ms 158280 KB Output is correct
10 Correct 274 ms 155272 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 128200 KB Output is correct
2 Correct 113 ms 127336 KB Output is correct
3 Correct 128 ms 127680 KB Output is correct
4 Correct 118 ms 127328 KB Output is correct
5 Correct 113 ms 127308 KB Output is correct
6 Correct 130 ms 127668 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 125512 KB Output is correct
2 Correct 60 ms 125448 KB Output is correct
3 Correct 59 ms 125516 KB Output is correct
4 Correct 58 ms 125512 KB Output is correct
5 Correct 59 ms 125424 KB Output is correct
6 Correct 59 ms 125528 KB Output is correct
7 Correct 58 ms 125488 KB Output is correct
8 Correct 305 ms 191712 KB Output is correct
9 Correct 310 ms 190796 KB Output is correct
10 Correct 238 ms 143636 KB Output is correct
11 Correct 233 ms 143252 KB Output is correct
12 Correct 230 ms 168128 KB Output is correct
13 Correct 237 ms 168780 KB Output is correct
14 Correct 284 ms 141476 KB Output is correct
15 Correct 383 ms 162180 KB Output is correct
16 Correct 370 ms 158280 KB Output is correct
17 Correct 274 ms 155272 KB Output is correct
18 Correct 144 ms 128200 KB Output is correct
19 Correct 113 ms 127336 KB Output is correct
20 Correct 128 ms 127680 KB Output is correct
21 Correct 118 ms 127328 KB Output is correct
22 Correct 113 ms 127308 KB Output is correct
23 Correct 130 ms 127668 KB Output is correct
24 Correct 343 ms 183288 KB Output is correct
25 Correct 381 ms 183688 KB Output is correct
26 Correct 324 ms 182564 KB Output is correct
27 Correct 256 ms 143120 KB Output is correct
28 Correct 416 ms 152004 KB Output is correct
29 Correct 325 ms 137536 KB Output is correct