oj.uz

Submission #656788

# Submission time Handle Problem Language Result Execution time Memory
656788 2022-11-08T08:36:07 Z Mike4235 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 318 ms 255956 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 list1;
    ReversedTrie list2;
    for (int i = 1; i <= n; i++) {
        list1.add_string(v[i - 1], i);
        list2.add_string(v[i - 1], i);
    }

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188108 KB Output is correct
2 Correct 82 ms 188068 KB Output is correct
3 Correct 82 ms 188092 KB Output is correct
4 Correct 81 ms 188132 KB Output is correct
5 Correct 84 ms 188156 KB Output is correct
6 Correct 82 ms 188140 KB Output is correct
7 Correct 81 ms 188176 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 255956 KB Output is correct
2 Correct 254 ms 252808 KB Output is correct
3 Correct 233 ms 205960 KB Output is correct
4 Correct 229 ms 205824 KB Output is correct
5 Correct 242 ms 230364 KB Output is correct
6 Correct 245 ms 230968 KB Output is correct
7 Correct 146 ms 203916 KB Output is correct
8 Correct 255 ms 224544 KB Output is correct
9 Correct 221 ms 220464 KB Output is correct
10 Correct 190 ms 217504 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 194796 KB Output is correct
2 Correct 100 ms 191860 KB Output is correct
3 Correct 104 ms 194092 KB Output is correct
4 Correct 100 ms 193640 KB Output is correct
5 Correct 103 ms 191940 KB Output is correct
6 Correct 106 ms 194016 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188108 KB Output is correct
2 Correct 82 ms 188068 KB Output is correct
3 Correct 82 ms 188092 KB Output is correct
4 Correct 81 ms 188132 KB Output is correct
5 Correct 84 ms 188156 KB Output is correct
6 Correct 82 ms 188140 KB Output is correct
7 Correct 81 ms 188176 KB Output is correct
8 Correct 251 ms 255956 KB Output is correct
9 Correct 254 ms 252808 KB Output is correct
10 Correct 233 ms 205960 KB Output is correct
11 Correct 229 ms 205824 KB Output is correct
12 Correct 242 ms 230364 KB Output is correct
13 Correct 245 ms 230968 KB Output is correct
14 Correct 146 ms 203916 KB Output is correct
15 Correct 255 ms 224544 KB Output is correct
16 Correct 221 ms 220464 KB Output is correct
17 Correct 190 ms 217504 KB Output is correct
18 Correct 108 ms 194796 KB Output is correct
19 Correct 100 ms 191860 KB Output is correct
20 Correct 104 ms 194092 KB Output is correct
21 Correct 100 ms 193640 KB Output is correct
22 Correct 103 ms 191940 KB Output is correct
23 Correct 106 ms 194016 KB Output is correct
24 Correct 255 ms 245248 KB Output is correct
25 Correct 261 ms 245576 KB Output is correct
26 Correct 244 ms 244612 KB Output is correct
27 Correct 318 ms 205516 KB Output is correct
28 Correct 245 ms 213412 KB Output is correct
29 Correct 156 ms 201968 KB Output is correct