oj.uz

Submission #1032860

# Submission time Handle Problem Language Result Execution time Memory
1032860 2024-07-24T10:03:46 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 520 ms 603532 KB 
#include <bits/stdc++.h>

using namespace std;

struct Pre
{
    struct node
    {
        int l, r;
        node* child[26];
        node ()
        {
            l = 1e9, r = 0;
            for (int i = 0; i < 26; i++) child[i] = NULL;
        }
    } *root;

    Pre ()
    {
        root = new node();
    }

    void add(string s, int idx)
    {
        node* cur = root;
        for (int i = 0; i < (int)s.size(); i++)
        {
            int id = s[i]-'A';
            if (cur->child[id] == NULL) cur->child[id] = new node();
            cur = cur->child[id];
            cur->l = min(cur->l, idx), cur->r = max(cur->r, idx);
        }
    }

    pair<int, int> get(string s)
    {
        node* cur = root;
        for (int i = 0; i < (int)s.size(); i++)
        {
            int id = s[i]-'A';
            if (cur->child[id] == NULL) return {-1, -1};
            cur = cur->child[id];
        }
        return {cur->l, cur->r};
    }
} pre;

struct Suf
{
    struct node
    {
        vector<int> v;
        node* child[26];
        node ()
        {
            for (int i = 0; i < 26; i++) child[i] = NULL;
        }
    } *root;

    Suf ()
    {
        root = new node();
    }

    void add(string s, int idx)
    {
        reverse(s.begin(), s.end());
        node* cur = root;
        for (int i = 0; i < (int)s.size(); i++)
        {
            int id = s[i]-'A';
            if (cur->child[id] == NULL) cur->child[id] = new node();
            cur = cur->child[id];
            cur->v.push_back(idx);
        }
    }

    void srt(node* cur = NULL)
    {
        if (cur == NULL) cur = root;
        sort(cur->v.begin(), cur->v.end());
        for (int i = 0; i < 26; i++)
            if (cur->child[i] != NULL) srt(cur->child[i]);
    }

    int get(string s, int l, int r)
    {
        reverse(s.begin(), s.end());
        node* cur = root;
        for (int i = 0; i < (int)s.size(); i++)
        {
            int id = s[i]-'A';
            if (cur->child[id] == NULL) return 0;
            cur = cur->child[id];
        }
        int L = lower_bound(cur->v.begin(), cur->v.end(), l)-cur->v.begin();
        int R = upper_bound(cur->v.begin(), cur->v.end(), r)-cur->v.begin();
        return R-L;
    }
} suf;

int main()
{    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m;
    cin >> n >> m;

    vector<string> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s.begin(), s.end());
    for (int i = 0; i < n; i++) pre.add(s[i], i), suf.add(s[i], i);
    suf.srt();

    while (m--)
    {
        string p, q;
        cin >> p >> q;
        pair<int, int> pr = pre.get(p);
        if (pr.first == -1) cout << "0\n";
        else cout << suf.get(q, pr.first, pr.second) << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 381 ms 530784 KB Output is correct
2 Correct 402 ms 502652 KB Output is correct
3 Correct 253 ms 443780 KB Output is correct
4 Correct 283 ms 422488 KB Output is correct
5 Correct 462 ms 594512 KB Output is correct
6 Correct 520 ms 603532 KB Output is correct
7 Correct 61 ms 16724 KB Output is correct
8 Correct 298 ms 360472 KB Output is correct
9 Correct 325 ms 304116 KB Output is correct
10 Correct 242 ms 293200 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3288 KB Output is correct
2 Correct 15 ms 3420 KB Output is correct
3 Correct 17 ms 3504 KB Output is correct
4 Correct 14 ms 2396 KB Output is correct
5 Correct 24 ms 3420 KB Output is correct
6 Correct 20 ms 3164 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 381 ms 530784 KB Output is correct
9 Correct 402 ms 502652 KB Output is correct
10 Correct 253 ms 443780 KB Output is correct
11 Correct 283 ms 422488 KB Output is correct
12 Correct 462 ms 594512 KB Output is correct
13 Correct 520 ms 603532 KB Output is correct
14 Correct 61 ms 16724 KB Output is correct
15 Correct 298 ms 360472 KB Output is correct
16 Correct 325 ms 304116 KB Output is correct
17 Correct 242 ms 293200 KB Output is correct
18 Correct 18 ms 3288 KB Output is correct
19 Correct 15 ms 3420 KB Output is correct
20 Correct 17 ms 3504 KB Output is correct
21 Correct 14 ms 2396 KB Output is correct
22 Correct 24 ms 3420 KB Output is correct
23 Correct 20 ms 3164 KB Output is correct
24 Correct 360 ms 434624 KB Output is correct
25 Correct 368 ms 434772 KB Output is correct
26 Correct 355 ms 429700 KB Output is correct
27 Correct 280 ms 364372 KB Output is correct
28 Correct 143 ms 74684 KB Output is correct
29 Correct 61 ms 12112 KB Output is correct