oj.uz

Submission #918872

# Submission time Handle Problem Language Result Execution time Memory
918872 2024-01-30T15:21:06 Z Ska Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 189 ms 194384 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int val(char c) {
    switch(c) {
        case 'A': return 0;
        case 'G': return 1;
        case 'C': return 2;
        default: return 3;
    }
}

struct Trie {
    struct Node {
        Node* child[4];
        int l, r;
        Node(): l(N), r(0) {
            fill(begin(child), end(child), nullptr);
        }
    };

    Node* root;
    Trie() {
        root = new Node();
    }

    void add(string &s, int id) {
        Node* p = root;
        for (auto &x: s) {
            int c = val(x);
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
    }

    pair<int, int> query(string &s) {
        pair<int, int> res = {0, N};
        Node* p = root;
        for (auto &x: s) {
            int c = val(x);
            if (p->child[c] == nullptr) return res;
            p = p->child[c];
            res.first = max(res.first, p->l);
            res.second = min(res.second, p->r);
        }
        return res;
    }
};

struct ReversedTrie {
    struct Node {
        Node* child[4];
        vector<int> ids;
        Node() {
            fill(begin(child), end(child), nullptr);
        }
    };

    Node* root;
    ReversedTrie() {
        root = new Node();
    }

    void add(string &s, int id) {
        Node* p = root;
        for (int i = s.size() - 1; i >= 0; --i) {
            int c = val(s[i]);
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
            p->ids.emplace_back(id);
        }
    }

    int query(string &s, pair<int, int> range) {
        Node* p = root;
        for (int i = s.size() - 1; i >= 0; --i) {
            int c = val(s[i]);
            if (p->child[c] == nullptr) return 0;
            p = p->child[c];
        }
        int l = lower_bound(p->ids.begin(), p->ids.end(), range.first) - p->ids.begin();
        int r = upper_bound(p->ids.begin(), p->ids.end(), range.second) - p->ids.begin() - 1;
        return r - l + 1;
    }
};

int n, q;
string a[N];
Trie trie1;
ReversedTrie trie2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        trie1.add(a[i], i);
        trie2.add(a[i], i);
    }

    while (q--) {
        string p, q;
        cin >> p >> q;
        auto range = trie1.query(p);
        if (!range.first) {
            cout << 0 << '\n';
            continue;
        }
        cout << trie2.query(q, range) << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 1 ms 3416 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 194384 KB Output is correct
2 Correct 179 ms 184724 KB Output is correct
3 Correct 102 ms 111952 KB Output is correct
4 Correct 100 ms 107164 KB Output is correct
5 Correct 165 ms 178768 KB Output is correct
6 Correct 162 ms 181328 KB Output is correct
7 Correct 40 ms 19024 KB Output is correct
8 Correct 146 ms 117836 KB Output is correct
9 Correct 127 ms 101200 KB Output is correct
10 Correct 91 ms 96180 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4848 KB Output is correct
2 Correct 15 ms 4952 KB Output is correct
3 Correct 18 ms 4696 KB Output is correct
4 Correct 13 ms 4508 KB Output is correct
5 Correct 15 ms 4696 KB Output is correct
6 Correct 19 ms 4696 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 1 ms 3416 KB Output is correct
5 Correct 2 ms 3416 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Correct 189 ms 194384 KB Output is correct
9 Correct 179 ms 184724 KB Output is correct
10 Correct 102 ms 111952 KB Output is correct
11 Correct 100 ms 107164 KB Output is correct
12 Correct 165 ms 178768 KB Output is correct
13 Correct 162 ms 181328 KB Output is correct
14 Correct 40 ms 19024 KB Output is correct
15 Correct 146 ms 117836 KB Output is correct
16 Correct 127 ms 101200 KB Output is correct
17 Correct 91 ms 96180 KB Output is correct
18 Correct 18 ms 4848 KB Output is correct
19 Correct 15 ms 4952 KB Output is correct
20 Correct 18 ms 4696 KB Output is correct
21 Correct 13 ms 4508 KB Output is correct
22 Correct 15 ms 4696 KB Output is correct
23 Correct 19 ms 4696 KB Output is correct
24 Correct 167 ms 160836 KB Output is correct
25 Correct 172 ms 160776 KB Output is correct
26 Correct 170 ms 158860 KB Output is correct
27 Correct 95 ms 94204 KB Output is correct
28 Correct 118 ms 38920 KB Output is correct
29 Correct 50 ms 12072 KB Output is correct