oj.uz

Submission #682081

# Submission time Handle Problem Language Result Execution time Memory
682081 2023-01-15T15:31:01 Z Pannda Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 281 ms 178536 KB 
#include <bits/stdc++.h>
using namespace std;

struct Trie {
    vector<array<int, 4>> trie;
    vector<vector<int>> mem;

    Trie() : trie(1), mem(1) {}

    void add(int u, string &s, int i) {
        for (auto c : s) {
            if (!trie[u][c]) {
                trie[u][c] = trie.size();
                trie.push_back({});
                mem.push_back({});
            }
            u = trie[u][c];
            mem[u].push_back(i);
        }
    }

    int get(int u, string &s) {
        for (auto c : s) {
            if (!trie[u][c]) {
                return 0;
            }
            u = trie[u][c];
        }
        return u;
    }
};

void alter(string &s) {
    for (auto &ch : s) {
        if (ch == 'A') ch = 0;
        if (ch == 'G') ch = 1;
        if (ch == 'C') ch = 2;
        if (ch == 'U') ch = 3;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    Trie pref, suff;
    vector<string> s(n);

    for (int i = 0; i < n; i++) {
        cin >> s[i];
        alter(s[i]);
    }

    sort(s.begin(), s.end());

    for (int i = 0; i < n; i++) {
        pref.add(0, s[i], i);
        reverse(s[i].begin(), s[i].end());
        suff.add(0, s[i], i);
    }

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

        alter(p);
        alter(s);
        reverse(s.begin(), s.end());
        int pid = pref.get(0, p);
        int sid = suff.get(0, s);

        int l = pref.mem[pid].front(), r = pref.mem[pid].back();
        cout << upper_bound(suff.mem[sid].begin(), suff.mem[sid].end(), r) - lower_bound(suff.mem[sid].begin(), suff.mem[sid].end(), l) << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 156484 KB Output is correct
2 Correct 236 ms 148480 KB Output is correct
3 Correct 220 ms 154220 KB Output is correct
4 Correct 219 ms 147220 KB Output is correct
5 Correct 268 ms 175948 KB Output is correct
6 Correct 281 ms 178536 KB Output is correct
7 Correct 63 ms 24356 KB Output is correct
8 Correct 235 ms 131984 KB Output is correct
9 Correct 211 ms 106836 KB Output is correct
10 Correct 179 ms 102812 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3248 KB Output is correct
2 Correct 20 ms 2696 KB Output is correct
3 Correct 25 ms 2900 KB Output is correct
4 Correct 17 ms 2516 KB Output is correct
5 Correct 26 ms 2724 KB Output is correct
6 Correct 25 ms 2900 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 237 ms 156484 KB Output is correct
9 Correct 236 ms 148480 KB Output is correct
10 Correct 220 ms 154220 KB Output is correct
11 Correct 219 ms 147220 KB Output is correct
12 Correct 268 ms 175948 KB Output is correct
13 Correct 281 ms 178536 KB Output is correct
14 Correct 63 ms 24356 KB Output is correct
15 Correct 235 ms 131984 KB Output is correct
16 Correct 211 ms 106836 KB Output is correct
17 Correct 179 ms 102812 KB Output is correct
18 Correct 24 ms 3248 KB Output is correct
19 Correct 20 ms 2696 KB Output is correct
20 Correct 25 ms 2900 KB Output is correct
21 Correct 17 ms 2516 KB Output is correct
22 Correct 26 ms 2724 KB Output is correct
23 Correct 25 ms 2900 KB Output is correct
24 Correct 251 ms 130356 KB Output is correct
25 Correct 246 ms 130572 KB Output is correct
26 Correct 226 ms 129176 KB Output is correct
27 Correct 210 ms 128500 KB Output is correct
28 Correct 182 ms 42832 KB Output is correct
29 Correct 82 ms 16484 KB Output is correct