oj.uz

Submission #847313

# Submission time Handle Problem Language Result Execution time Memory
847313 2023-09-09T13:18:44 Z Szil Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 217 ms 196436 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using RNA = vector<int>;

const int MAXN = 100'001;

struct Trie {

    static constexpr int N = 4;

    struct TrieNode {
        TrieNode *next[N];
        int st = MAXN;
        int en = -1;
    };

    TrieNode *root;

    Trie() {
        root = new TrieNode();
    }

    void add_string(const RNA &s, int index) {
        TrieNode *curr = root;
        for (int c : s) {
            if (!curr->next[c]) {
                curr->next[c] = new TrieNode();
            }

            curr = curr->next[c];
            curr->st = min(curr->st, index);
            curr->en = max(curr->en, index);
        }
    }

    pair<int, int> get_bounds(const RNA &s) const {
        TrieNode *curr = root;
        for (int c : s) {
            if (!curr->next[c]) {
                return {-1, -1};
            }

            curr = curr->next[c];
        }
        return {curr->st, curr->en};
    }
};

struct PersistentTrie {

    static constexpr int N = 4;

    struct PersistentTrieNode {
        PersistentTrieNode *next[N];
        int cnt = 0;

        PersistentTrieNode *get_copy() {
            PersistentTrieNode *res = new PersistentTrieNode();

            res->cnt = cnt;
            for (int i = 0; i < N; i++) {
                res->next[i] = next[i];
            }

            return res;
        }
    };

    vector<PersistentTrieNode*> roots;

    PersistentTrie() {
        roots.emplace_back(new PersistentTrieNode());
    }

    void add_string(const RNA &s) {
        roots.emplace_back(roots.back()->get_copy());
        PersistentTrieNode *curr = roots.back();

        for (int i = s.size() - 1; i >= 0; i--) {
            if (curr->next[s[i]]) {
                curr->next[s[i]] = curr->next[s[i]]->get_copy();
            } else {
                curr->next[s[i]] = new PersistentTrieNode();
            }

            curr = curr->next[s[i]];
            curr->cnt++;
        }
    }

    int get_count(const RNA &s, int time) {
        if (time < 0) return 0;

        PersistentTrieNode *curr = roots[time];

        for (int i = s.size() - 1; i >= 0; i--) {
            if (!curr->next[s[i]]) {
                return 0;
            }

            curr = curr->next[s[i]];
        }
        
        return curr->cnt;
    }
};

RNA string_to_rna(const string &s) {
    RNA res;
    for (char c : s) {
        if (c == 'A') {
            res.emplace_back(0);
        } else if (c == 'G') {
            res.emplace_back(1);
        } else if (c == 'C') {
            res.emplace_back(2);
        } else if (c == 'U') {
            res.emplace_back(3);
        }
    }
    return res;
}

void solve() {
    int n, q; cin >> n >> q;
    vector<RNA> v(n+1);
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        v[i] = string_to_rna(s);
    }
    sort(v.begin(), v.end());

    Trie trie;
    PersistentTrie ptrie;

    for (int i = 1; i <= n; i++) {
        trie.add_string(v[i], i);
        ptrie.add_string(v[i]);
    }

    while (q--) {
        string as, bs; cin >> as >> bs;
        RNA a = string_to_rna(as);
        RNA b = string_to_rna(bs);

        auto [l, r] = trie.get_bounds(a);
        int ans = ptrie.get_count(b, r) - ptrie.get_count(b, l-1);
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 105304 KB Output is correct
2 Correct 138 ms 106380 KB Output is correct
3 Correct 189 ms 196436 KB Output is correct
4 Correct 161 ms 192592 KB Output is correct
5 Correct 123 ms 122960 KB Output is correct
6 Correct 122 ms 124748 KB Output is correct
7 Correct 115 ms 79488 KB Output is correct
8 Correct 163 ms 138436 KB Output is correct
9 Correct 152 ms 132344 KB Output is correct
10 Correct 118 ms 132328 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10744 KB Output is correct
2 Correct 29 ms 8916 KB Output is correct
3 Correct 28 ms 9684 KB Output is correct
4 Correct 24 ms 8920 KB Output is correct
5 Correct 23 ms 8920 KB Output is correct
6 Correct 30 ms 9936 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 129 ms 105304 KB Output is correct
9 Correct 138 ms 106380 KB Output is correct
10 Correct 189 ms 196436 KB Output is correct
11 Correct 161 ms 192592 KB Output is correct
12 Correct 123 ms 122960 KB Output is correct
13 Correct 122 ms 124748 KB Output is correct
14 Correct 115 ms 79488 KB Output is correct
15 Correct 163 ms 138436 KB Output is correct
16 Correct 152 ms 132344 KB Output is correct
17 Correct 118 ms 132328 KB Output is correct
18 Correct 32 ms 10744 KB Output is correct
19 Correct 29 ms 8916 KB Output is correct
20 Correct 28 ms 9684 KB Output is correct
21 Correct 24 ms 8920 KB Output is correct
22 Correct 23 ms 8920 KB Output is correct
23 Correct 30 ms 9936 KB Output is correct
24 Correct 159 ms 106956 KB Output is correct
25 Correct 187 ms 107052 KB Output is correct
26 Correct 141 ms 107052 KB Output is correct
27 Correct 164 ms 180636 KB Output is correct
28 Correct 217 ms 115676 KB Output is correct
29 Correct 145 ms 63432 KB Output is correct