oj.uz

Submission #1002436

# Submission time Handle Problem Language Result Execution time Memory
1002436 2024-06-19T14:55:50 Z nmts Selling RNA Strands (JOI16_selling_rna) C++17
35 / 100
 1500 ms 267748 KB 
#include <bits/stdc++.h>

#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pii pair<int, int>
#define fi first
#define se second
#define endl '\n'
#define int long long

const int maxn = 1e6 + 6;
const int INF = 1e9;

using namespace std;

int n, m;
string s[maxn];

int get_val(char ch) {
    return (ch == 'A' ? 1 : ch == 'G' ? 2 : ch == 'C' ? 3 : 4);
}

struct Trie {
    struct Node {
        Node* child[5];
        int l, r;
        int exits;
        Node() {
            for (int i = 1; i <= 4; ++i) child[i] = NULL;
            l = INF;
            r = -INF;
            exits = 0;
        }
    };

    Node* root;

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

    void add(string s, int id) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) p->child[val] = new Node;
            p = p->child[val];
            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
        p->exits++;
    }

    pii get_range(string s) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) return {-1, -1};
            p = p->child[val];
        }
        return {p->l, p->r};
    }
};

struct RTrie {
    struct Node {
        Node* child[5];
        vector<int> exits;
        Node() {
            for (int i = 1; i <= 4; ++i) child[i] = NULL;
            exits.clear();
        }
    };

    Node* root;

    RTrie() {
        root = new Node;
    };

    void add(string s, int id) {
        Node* p = root;
        for (char c : s) {
            p->exits.push_back(id);
            int val = get_val(c);
            if (p->child[val] == NULL) p->child[val] = new Node;
            p = p->child[val];
        }
        p->exits.push_back(id);
    }

    int get_ans(string s, int u, int v) {
        Node* p = root;
        for (char c : s) {
            int val = get_val(c);
            if (p->child[val] == NULL) return 0;
            p = p->child[val];
        }

        sort(p->exits.begin(), p->exits.end());
        int l = lower_bound(p->exits.begin(), p->exits.end(), u) - p->exits.begin();
        int r = upper_bound(p->exits.begin(), p->exits.end(), v) - p->exits.begin() - 1;

        return r - l + 1;
    }
};

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) cin >> s[i];

    sort(s + 1, s + n + 1);

    Trie tr;
    RTrie Rtr;
    for (int i = 1; i <= n; ++i) {
        tr.add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        Rtr.add(s[i], i);
    }

    while (m--) {
        string a, b;
        cin >> a >> b;
        pii it = tr.get_range(a);
        reverse(b.begin(), b.end());
        if (it.fi == -1) cout << 0 << '\n';
        else cout << Rtr.get_ans(b, it.fi, it.se) << '\n';
    }
}

int32_t main() {
    faster;
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 21 ms 31780 KB Output is correct
3 Correct 13 ms 31576 KB Output is correct
4 Correct 14 ms 31580 KB Output is correct
5 Correct 16 ms 31548 KB Output is correct
6 Correct 15 ms 31580 KB Output is correct
7 Correct 14 ms 31580 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 253524 KB Output is correct
2 Correct 213 ms 242280 KB Output is correct
3 Correct 270 ms 210504 KB Output is correct
4 Correct 309 ms 202108 KB Output is correct
5 Correct 190 ms 264124 KB Output is correct
6 Correct 197 ms 267748 KB Output is correct
7 Correct 140 ms 54608 KB Output is correct
8 Correct 156 ms 186008 KB Output is correct
9 Correct 147 ms 164808 KB Output is correct
10 Correct 460 ms 158716 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 33800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 31576 KB Output is correct
2 Correct 21 ms 31780 KB Output is correct
3 Correct 13 ms 31576 KB Output is correct
4 Correct 14 ms 31580 KB Output is correct
5 Correct 16 ms 31548 KB Output is correct
6 Correct 15 ms 31580 KB Output is correct
7 Correct 14 ms 31580 KB Output is correct
8 Correct 204 ms 253524 KB Output is correct
9 Correct 213 ms 242280 KB Output is correct
10 Correct 270 ms 210504 KB Output is correct
11 Correct 309 ms 202108 KB Output is correct
12 Correct 190 ms 264124 KB Output is correct
13 Correct 197 ms 267748 KB Output is correct
14 Correct 140 ms 54608 KB Output is correct
15 Correct 156 ms 186008 KB Output is correct
16 Correct 147 ms 164808 KB Output is correct
17 Correct 460 ms 158716 KB Output is correct
18 Execution timed out 1577 ms 33800 KB Time limit exceeded
19 Halted 0 ms 0 KB -