oj.uz

Submission #1002432

# Submission time Handle Problem Language Result Execution time Memory
1002432 2024-06-19T14:52:45 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 226 ms 256080 KB 
#include <bits/stdc++.h>

using namespace std;

int get_val(char f) {
    if (f == 'A') return 0;
    if (f == 'G') return 1;
    if (f == 'C') return 2;
    return 3;
}

char get_char(int x) {
    if (x == 0) return 'A';
    if (x == 1) return 'G';
    if (x == 2) return 'C';
    return 'U';
}

const int NUMBEROFNODES = 2e6 + 5;
const int INF = 1e9;
struct Trie{
    struct Node{
        int child[4];
        int l, r;
        int exist;
    } nodes[NUMBEROFNODES];

    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].l = INF; nodes[0].r = -INF;
        nodes[0].exist = 0;
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].l = INF; nodes[cur].r = -INF;
        nodes[cur].exist = 0;
        return cur;
    }

    void add_string(string s, int id) {
        int pos = 0;
        for (auto f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
            pos = nodes[pos].child[c];

            nodes[pos].l = min(nodes[pos].l, id);
            nodes[pos].r = max(nodes[pos].r, id);
        }
        nodes[pos].exist++;
    }

    pair<int, int> get_range(string s) {
        int pos = 0;
        for (auto f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) return {-1, -1};
            pos = nodes[pos].child[c];
        }
        return {nodes[pos].l, nodes[pos].r};
    }

    void dfs(int pos, string& current_string, vector<string>& res) {
        for (int i = 1; i <= nodes[pos].exist; i++) res.push_back(current_string);

        for (int i = 0; i < 4; i++) if (nodes[pos].child[i] != -1) {
            current_string += get_char(i);
            dfs(nodes[pos].child[i], current_string, res);
            current_string.pop_back();
        }
    }

    vector<string> sort_strings() {
        vector<string> res;
        string current_string = "";
        dfs(0, current_string, res);
        return res;
    }
};

struct ReversedTrie{
    struct Node{
        int child[4];
        vector<int> ids;
    } nodes[NUMBEROFNODES];

    int cur;
    ReversedTrie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].ids.clear();
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].ids.clear();
        return cur;
    }

    void add_string(string s, int id) {
        reverse(s.begin(), s.end());
        int pos = 0;
        for (auto f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
            pos = nodes[pos].child[c];
            nodes[pos].ids.push_back(id);
        }
    }

    int query(string s, pair<int, int> range) {
        reverse(s.begin(), s.end());
        int pos = 0;
        for (auto f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) return 0;
            pos = nodes[pos].child[c];
        }

        int l = lower_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.first) - nodes[pos].ids.begin();
        int r = upper_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.second) - nodes[pos].ids.begin() - 1;

        return r - l + 1;
    }
};

vector<string> sort_strings(vector<string> v) {
    Trie list;
    for (auto s : v) list.add_string(s, -1);
    return list.sort_strings();
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<string> v;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }
    v = sort_strings(v);

    Trie trie1;
    ReversedTrie trie2;
    for (int i = 1; i <= n; i++) {
        trie1.add_string(v[i - 1], i);
        trie2.add_string(v[i - 1], i);
    }

    while (m--) {
        string p, q;
        cin >> p >> q;

        pair<int, int> range = trie1.get_range(p);
        if (range.first == -1) cout << "0\n";
        else cout << trie2.query(q, range) << "\n";
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188184 KB Output is correct
2 Correct 89 ms 188240 KB Output is correct
3 Correct 89 ms 188244 KB Output is correct
4 Correct 98 ms 188116 KB Output is correct
5 Correct 91 ms 188292 KB Output is correct
6 Correct 89 ms 188208 KB Output is correct
7 Correct 90 ms 188240 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 256080 KB Output is correct
2 Correct 218 ms 252812 KB Output is correct
3 Correct 165 ms 206056 KB Output is correct
4 Correct 187 ms 205964 KB Output is correct
5 Correct 208 ms 230368 KB Output is correct
6 Correct 208 ms 231064 KB Output is correct
7 Correct 132 ms 203856 KB Output is correct
8 Correct 211 ms 224656 KB Output is correct
9 Correct 192 ms 220536 KB Output is correct
10 Correct 163 ms 217484 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 194824 KB Output is correct
2 Correct 101 ms 191948 KB Output is correct
3 Correct 105 ms 194248 KB Output is correct
4 Correct 103 ms 193664 KB Output is correct
5 Correct 105 ms 191952 KB Output is correct
6 Correct 106 ms 194244 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188184 KB Output is correct
2 Correct 89 ms 188240 KB Output is correct
3 Correct 89 ms 188244 KB Output is correct
4 Correct 98 ms 188116 KB Output is correct
5 Correct 91 ms 188292 KB Output is correct
6 Correct 89 ms 188208 KB Output is correct
7 Correct 90 ms 188240 KB Output is correct
8 Correct 226 ms 256080 KB Output is correct
9 Correct 218 ms 252812 KB Output is correct
10 Correct 165 ms 206056 KB Output is correct
11 Correct 187 ms 205964 KB Output is correct
12 Correct 208 ms 230368 KB Output is correct
13 Correct 208 ms 231064 KB Output is correct
14 Correct 132 ms 203856 KB Output is correct
15 Correct 211 ms 224656 KB Output is correct
16 Correct 192 ms 220536 KB Output is correct
17 Correct 163 ms 217484 KB Output is correct
18 Correct 106 ms 194824 KB Output is correct
19 Correct 101 ms 191948 KB Output is correct
20 Correct 105 ms 194248 KB Output is correct
21 Correct 103 ms 193664 KB Output is correct
22 Correct 105 ms 191952 KB Output is correct
23 Correct 106 ms 194244 KB Output is correct
24 Correct 223 ms 245328 KB Output is correct
25 Correct 219 ms 245504 KB Output is correct
26 Correct 222 ms 244660 KB Output is correct
27 Correct 166 ms 205584 KB Output is correct
28 Correct 187 ms 213300 KB Output is correct
29 Correct 129 ms 201920 KB Output is correct