oj.uz

Submission #693097

# Submission time Handle Problem Language Result Execution time Memory
693097 2023-02-02T11:30:59 Z horiseun Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 341 ms 455048 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <string>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, m, nx[2][2000005][30], x[2000005], y[2000005], idx1, idx2;
vector<int> v[2000005];
string s[2000005];

void update1(string curr, int pos) {
    int nd = 0;
    for (int i = 0; i < curr.size(); i++) {
        if (!nx[0][nd][curr[i] - 'A']) nx[0][nd][curr[i] - 'A'] = idx1++; 
        x[nd] = min(x[nd], pos);
        y[nd] = max(y[nd], pos);
        nd = nx[0][nd][curr[i] - 'A'];
    }
    x[nd] = min(x[nd], pos);
    y[nd] = max(y[nd], pos);
}

void update2(string curr, int pos) {
    int nd = 0;
    for (int i = curr.size() - 1; i >= 0; i--) {
        if (!nx[1][nd][curr[i] - 'A']) nx[1][nd][curr[i] - 'A'] = idx2++;
        v[nd].push_back(pos);
        nd = nx[1][nd][curr[i] - 'A'];
    }
    v[nd].push_back(pos);
}

pair<int, int> query1(string curr) {
    int nd = 0;
    for (int i = 0; i < curr.size(); i++) {
        if (!nx[0][nd][curr[i] - 'A']) return {-1, -1};
        nd = nx[0][nd][curr[i] - 'A'];
    }
    return {x[nd], y[nd]};
}

int query2(string curr, int l, int r) {
    if (l == -1 || r == -1) return 0;
    int nd = 0;
    for (int i = curr.size() - 1; i >= 0; i--) {
        if (!nx[1][nd][curr[i] - 'A']) return 0;
        nd = nx[1][nd][curr[i] - 'A'];
    }
    return (upper_bound(v[nd].begin(), v[nd].end(), r) - lower_bound(v[nd].begin(), v[nd].end(), l));
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    sort(s, s + n);

    fill(x, x + 2000005, 1e9);
    idx1 = 1, idx2 = 1;
    for (int i = 0; i < n; i++) {
        update1(s[i], i);
        update2(s[i], i);
    }
    for (int i = 0; i < m; i++) {
        string pr, su; cin >> pr >> su;
        pair<int, int> res = query1(pr);
        cout << query2(su, res.f, res.s) << "\n";
    }

}

Compilation message

selling_rna.cpp: In function 'void update1(std::string, int)':
selling_rna.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < curr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
selling_rna.cpp: In function 'std::pair<int, int> query1(std::string)':
selling_rna.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < curr.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 117692 KB Output is correct
2 Correct 57 ms 117772 KB Output is correct
3 Correct 52 ms 117764 KB Output is correct
4 Correct 53 ms 117692 KB Output is correct
5 Correct 59 ms 117716 KB Output is correct
6 Correct 53 ms 117656 KB Output is correct
7 Correct 56 ms 117744 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 416756 KB Output is correct
2 Correct 319 ms 400988 KB Output is correct
3 Correct 233 ms 370804 KB Output is correct
4 Correct 229 ms 358864 KB Output is correct
5 Correct 341 ms 450120 KB Output is correct
6 Correct 314 ms 455048 KB Output is correct
7 Correct 115 ms 133588 KB Output is correct
8 Correct 320 ms 324444 KB Output is correct
9 Correct 264 ms 292608 KB Output is correct
10 Correct 216 ms 285608 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 119252 KB Output is correct
2 Correct 76 ms 119500 KB Output is correct
3 Correct 80 ms 119364 KB Output is correct
4 Correct 73 ms 118928 KB Output is correct
5 Correct 85 ms 119460 KB Output is correct
6 Correct 81 ms 119356 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 117692 KB Output is correct
2 Correct 57 ms 117772 KB Output is correct
3 Correct 52 ms 117764 KB Output is correct
4 Correct 53 ms 117692 KB Output is correct
5 Correct 59 ms 117716 KB Output is correct
6 Correct 53 ms 117656 KB Output is correct
7 Correct 56 ms 117744 KB Output is correct
8 Correct 336 ms 416756 KB Output is correct
9 Correct 319 ms 400988 KB Output is correct
10 Correct 233 ms 370804 KB Output is correct
11 Correct 229 ms 358864 KB Output is correct
12 Correct 341 ms 450120 KB Output is correct
13 Correct 314 ms 455048 KB Output is correct
14 Correct 115 ms 133588 KB Output is correct
15 Correct 320 ms 324444 KB Output is correct
16 Correct 264 ms 292608 KB Output is correct
17 Correct 216 ms 285608 KB Output is correct
18 Correct 80 ms 119252 KB Output is correct
19 Correct 76 ms 119500 KB Output is correct
20 Correct 80 ms 119364 KB Output is correct
21 Correct 73 ms 118928 KB Output is correct
22 Correct 85 ms 119460 KB Output is correct
23 Correct 81 ms 119356 KB Output is correct
24 Correct 300 ms 363272 KB Output is correct
25 Correct 311 ms 363328 KB Output is correct
26 Correct 335 ms 360316 KB Output is correct
27 Correct 222 ms 326748 KB Output is correct
28 Correct 224 ms 164768 KB Output is correct
29 Correct 128 ms 126572 KB Output is correct