oj.uz

Submission #521574

# Submission time Handle Problem Language Result Execution time Memory
521574 2022-02-02T12:16:04 Z tengiz05 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 900 ms 102144 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 P = 1E9 + 7, M = 31;

struct Node {
    Node *to[4];
    int mn, mx;
    Node() {
        mn = 1E9, mx = 0;
        to[0] = to[1] = to[2] = to[3] = nullptr;
    }
};
void add(Node *u, std::string &s, int i, int p) {
    if (i == int(s.size())) {
        u->mn = std::min(u->mn, p);
        u->mx = std::max(u->mx, p);
        return;
    }
    int x = std::string("AGCU").find(s[i]);
    if (u->to[x] == nullptr) {
        u->to[x] = new Node();
    }
    add(u->to[x], s, i + 1, p);
    u->mn = std::min(u->mn, p);
    u->mx = std::max(u->mx, p);
}
std::pair<int, int> find(Node *u, std::string &s, int i) {
    if (i == int(s.size())) {
        return {u->mn, u->mx};
    }
    int x = std::string("AGCU").find(s[i]);
    if (u->to[x] == nullptr) {
        return {-1, -1};
    }
    return find(u->to[x], s, i + 1);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::string> s(n);
    Node *root = new Node();
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }
    
    std::sort(s.begin(), s.end());
    for (int i = 0; i < n; i++) {
        add(root, s[i], 0, i);
    }
    
    std::vector<std::tuple<int, int, int, int>> Q;
    std::vector<int> f;
    
    for (int i = 0; i < m; i++) {
        std::string p, q;
        std::cin >> p >> q;
        auto [l, r] = find(root, p, 0);
        if (l == -1) {
            continue;
        }
        r++;
        i64 H = 0;
        for (char c : q) {
            H *= M;
            H += std::string("AGCU").find(c) + 1;
            H %= P;
        }
        Q.emplace_back(l, H, i, -1);
        Q.emplace_back(r, H, i, 1);
        f.push_back(H);
    }
    for (int i = 0; i < n; i++) {
        i64 h = 0, pw = 1;
        for (int j = int(s[i].size()) - 1; j >= 0; j--) {
            h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
            pw *= M;
            pw %= P;
            f.push_back(h);
        }
    }
    
    std::sort(f.begin(), f.end());
    f.erase(std::unique(f.begin(), f.end()), f.end());
    
    std::sort(Q.begin(), Q.end());
    
    std::vector<int> ans(m);
    
    std::vector<int> cnt(f.size());
    int j = 0;
    for (int i = 0; i < n; i++) {
        int p, H, id, t;
        while (j < int(Q.size())) {
            std::tie(p, H, id, t) = Q[j];
            if (p != i) {
                break;
            }
            H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
            ans[id] += t * cnt[H];
            j++;
        }
        i64 h = 0, pw = 1;
        for (int j = int(s[i].size()) - 1; j >= 0; j--) {
            h = (h + pw * (std::string("AGCU").find(s[i][j]) + 1)) % P;
            pw *= M;
            pw %= P;
            int H = std::lower_bound(f.begin(), f.end(), h) - f.begin();
            cnt[H]++;
        }
    }
    while (j < int(Q.size())) {
        int p, H, id, t;
        std::tie(p, H, id, t) = Q[j];
        H = std::lower_bound(f.begin(), f.end(), H) - f.begin();
        ans[id] += t * cnt[H];
        j++;
    }
    
    for (int i = 0; i < m; i++) {
        std::cout << ans[i] << "\n";
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 19184 KB Output is correct
2 Correct 834 ms 18648 KB Output is correct
3 Correct 429 ms 102144 KB Output is correct
4 Correct 417 ms 97768 KB Output is correct
5 Correct 553 ms 68772 KB Output is correct
6 Correct 572 ms 69908 KB Output is correct
7 Correct 295 ms 10692 KB Output is correct
8 Correct 654 ms 47040 KB Output is correct
9 Correct 613 ms 40936 KB Output is correct
10 Correct 533 ms 40612 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5300 KB Output is correct
2 Correct 35 ms 3364 KB Output is correct
3 Correct 41 ms 4584 KB Output is correct
4 Correct 33 ms 4088 KB Output is correct
5 Correct 34 ms 3440 KB Output is correct
6 Correct 41 ms 4664 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 900 ms 19184 KB Output is correct
9 Correct 834 ms 18648 KB Output is correct
10 Correct 429 ms 102144 KB Output is correct
11 Correct 417 ms 97768 KB Output is correct
12 Correct 553 ms 68772 KB Output is correct
13 Correct 572 ms 69908 KB Output is correct
14 Correct 295 ms 10692 KB Output is correct
15 Correct 654 ms 47040 KB Output is correct
16 Correct 613 ms 40936 KB Output is correct
17 Correct 533 ms 40612 KB Output is correct
18 Correct 42 ms 5300 KB Output is correct
19 Correct 35 ms 3364 KB Output is correct
20 Correct 41 ms 4584 KB Output is correct
21 Correct 33 ms 4088 KB Output is correct
22 Correct 34 ms 3440 KB Output is correct
23 Correct 41 ms 4664 KB Output is correct
24 Correct 756 ms 18224 KB Output is correct
25 Correct 785 ms 19524 KB Output is correct
26 Correct 751 ms 17788 KB Output is correct
27 Correct 384 ms 85848 KB Output is correct
28 Correct 471 ms 25948 KB Output is correct
29 Correct 198 ms 14928 KB Output is correct