oj.uz

Submission #1049015

# Submission time Handle Problem Language Result Execution time Memory
1049015 2024-08-08T12:01:16 Z FanOfWilliamLin Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 211 ms 255932 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 78 ms 188104 KB Output is correct
2 Correct 77 ms 188244 KB Output is correct
3 Correct 79 ms 188280 KB Output is correct
4 Correct 77 ms 188244 KB Output is correct
5 Correct 106 ms 188244 KB Output is correct
6 Correct 76 ms 188312 KB Output is correct
7 Correct 86 ms 188244 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 255932 KB Output is correct
2 Correct 211 ms 252812 KB Output is correct
3 Correct 149 ms 206056 KB Output is correct
4 Correct 151 ms 205964 KB Output is correct
5 Correct 176 ms 230500 KB Output is correct
6 Correct 201 ms 231048 KB Output is correct
7 Correct 113 ms 203856 KB Output is correct
8 Correct 183 ms 224436 KB Output is correct
9 Correct 155 ms 220556 KB Output is correct
10 Correct 143 ms 217652 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 194772 KB Output is correct
2 Correct 91 ms 191948 KB Output is correct
3 Correct 89 ms 194244 KB Output is correct
4 Correct 88 ms 193736 KB Output is correct
5 Correct 88 ms 192084 KB Output is correct
6 Correct 91 ms 194080 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 188104 KB Output is correct
2 Correct 77 ms 188244 KB Output is correct
3 Correct 79 ms 188280 KB Output is correct
4 Correct 77 ms 188244 KB Output is correct
5 Correct 106 ms 188244 KB Output is correct
6 Correct 76 ms 188312 KB Output is correct
7 Correct 86 ms 188244 KB Output is correct
8 Correct 188 ms 255932 KB Output is correct
9 Correct 211 ms 252812 KB Output is correct
10 Correct 149 ms 206056 KB Output is correct
11 Correct 151 ms 205964 KB Output is correct
12 Correct 176 ms 230500 KB Output is correct
13 Correct 201 ms 231048 KB Output is correct
14 Correct 113 ms 203856 KB Output is correct
15 Correct 183 ms 224436 KB Output is correct
16 Correct 155 ms 220556 KB Output is correct
17 Correct 143 ms 217652 KB Output is correct
18 Correct 91 ms 194772 KB Output is correct
19 Correct 91 ms 191948 KB Output is correct
20 Correct 89 ms 194244 KB Output is correct
21 Correct 88 ms 193736 KB Output is correct
22 Correct 88 ms 192084 KB Output is correct
23 Correct 91 ms 194080 KB Output is correct
24 Correct 187 ms 245328 KB Output is correct
25 Correct 190 ms 245584 KB Output is correct
26 Correct 185 ms 244564 KB Output is correct
27 Correct 139 ms 205572 KB Output is correct
28 Correct 168 ms 213436 KB Output is correct
29 Correct 115 ms 202696 KB Output is correct