oj.uz

Submission #657588

# Submission time Handle Problem Language Result Execution time Memory
657588 2022-11-10T10:30:45 Z Mike4235 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 269 ms 255988 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 148 ms 188112 KB Output is correct
2 Correct 95 ms 188156 KB Output is correct
3 Correct 88 ms 188112 KB Output is correct
4 Correct 88 ms 188064 KB Output is correct
5 Correct 83 ms 188096 KB Output is correct
6 Correct 84 ms 188104 KB Output is correct
7 Correct 82 ms 188108 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 255988 KB Output is correct
2 Correct 262 ms 252760 KB Output is correct
3 Correct 236 ms 205896 KB Output is correct
4 Correct 254 ms 205832 KB Output is correct
5 Correct 243 ms 230308 KB Output is correct
6 Correct 248 ms 231028 KB Output is correct
7 Correct 162 ms 203848 KB Output is correct
8 Correct 249 ms 224524 KB Output is correct
9 Correct 226 ms 220356 KB Output is correct
10 Correct 203 ms 217452 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 194672 KB Output is correct
2 Correct 102 ms 191844 KB Output is correct
3 Correct 114 ms 194140 KB Output is correct
4 Correct 109 ms 193644 KB Output is correct
5 Correct 101 ms 191820 KB Output is correct
6 Correct 106 ms 194136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 188112 KB Output is correct
2 Correct 95 ms 188156 KB Output is correct
3 Correct 88 ms 188112 KB Output is correct
4 Correct 88 ms 188064 KB Output is correct
5 Correct 83 ms 188096 KB Output is correct
6 Correct 84 ms 188104 KB Output is correct
7 Correct 82 ms 188108 KB Output is correct
8 Correct 267 ms 255988 KB Output is correct
9 Correct 262 ms 252760 KB Output is correct
10 Correct 236 ms 205896 KB Output is correct
11 Correct 254 ms 205832 KB Output is correct
12 Correct 243 ms 230308 KB Output is correct
13 Correct 248 ms 231028 KB Output is correct
14 Correct 162 ms 203848 KB Output is correct
15 Correct 249 ms 224524 KB Output is correct
16 Correct 226 ms 220356 KB Output is correct
17 Correct 203 ms 217452 KB Output is correct
18 Correct 106 ms 194672 KB Output is correct
19 Correct 102 ms 191844 KB Output is correct
20 Correct 114 ms 194140 KB Output is correct
21 Correct 109 ms 193644 KB Output is correct
22 Correct 101 ms 191820 KB Output is correct
23 Correct 106 ms 194136 KB Output is correct
24 Correct 269 ms 245324 KB Output is correct
25 Correct 262 ms 245580 KB Output is correct
26 Correct 259 ms 244608 KB Output is correct
27 Correct 235 ms 205556 KB Output is correct
28 Correct 261 ms 213284 KB Output is correct
29 Correct 155 ms 201876 KB Output is correct