oj.uz

Submission #1070097

# Submission time Handle Problem Language Result Execution time Memory
1070097 2024-08-22T11:39:09 Z giaminh2211 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 214 ms 320660 KB 
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

struct Trie{
    struct node{
        vector<int> id;
        int child[26];
    };

    int n=-1;
    vector<node> trie;
    node tmp;

    int new_node(){
        ++n;
        trie.push_back(tmp);
        memset(trie[n].child, -1, sizeof(trie[n].child));
        return n;
    }
    
    Trie(){
    	new_node();
    }

    void add_string(string s, int val){
        int pos=0;
        for(char c: s){
            if(trie[pos].child[c-'A'] == -1){
            	int val=new_node();
                trie[pos].child[c-'A'] = n;
            }
            pos=trie[pos].child[c-'A'];
            trie[pos].id.push_back(val);
        }
    }

    int get(string s, int l, int r){ // s = suffix
        int pos=0;
        for(char c: s){
            if(trie[pos].child[c-'A'] == -1){
                return 0;
            }
            pos=trie[pos].child[c-'A'];
        }
        return upper_bound(begin(trie[pos].id), end(trie[pos].id), r)
            -  lower_bound(begin(trie[pos].id), end(trie[pos].id), l);
    }
};

int n, q;
const int N=2e5+13;
string a[N];
Trie trie;
string s, suf;

void scan(){
    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++){
        s=a[i];
        reverse(begin(s), end(s));
        trie.add_string(s, i);
    }
}

void solve(){
    while(q--){
        cin >> s >> suf;
        reverse(begin(suf), end(suf));
        int l=lower_bound(a+1, a+n+1, s)-a;
        ++s[s.size()-1];
        int r=lower_bound(a+1, a+n+1, s)-a-1;
        if(l <= r){
            cout << trie.get(suf, l, r);
        }
        else cout << 0;
        cout << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    scan();
    solve();
}

Compilation message

selling_rna.cpp: In member function 'void Trie::add_string(std::string, int)':
selling_rna.cpp:31:18: warning: unused variable 'val' [-Wunused-variable]
   31 |              int val=new_node();
      |                  ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 320660 KB Output is correct
2 Correct 194 ms 306576 KB Output is correct
3 Correct 41 ms 24660 KB Output is correct
4 Correct 43 ms 24520 KB Output is correct
5 Correct 165 ms 306336 KB Output is correct
6 Correct 166 ms 306612 KB Output is correct
7 Correct 29 ms 22220 KB Output is correct
8 Correct 128 ms 160676 KB Output is correct
9 Correct 105 ms 162956 KB Output is correct
10 Correct 84 ms 165484 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7892 KB Output is correct
2 Correct 18 ms 8400 KB Output is correct
3 Correct 21 ms 8028 KB Output is correct
4 Correct 16 ms 7772 KB Output is correct
5 Correct 18 ms 7768 KB Output is correct
6 Correct 21 ms 7768 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 196 ms 320660 KB Output is correct
9 Correct 194 ms 306576 KB Output is correct
10 Correct 41 ms 24660 KB Output is correct
11 Correct 43 ms 24520 KB Output is correct
12 Correct 165 ms 306336 KB Output is correct
13 Correct 166 ms 306612 KB Output is correct
14 Correct 29 ms 22220 KB Output is correct
15 Correct 128 ms 160676 KB Output is correct
16 Correct 105 ms 162956 KB Output is correct
17 Correct 84 ms 165484 KB Output is correct
18 Correct 22 ms 7892 KB Output is correct
19 Correct 18 ms 8400 KB Output is correct
20 Correct 21 ms 8028 KB Output is correct
21 Correct 16 ms 7772 KB Output is correct
22 Correct 18 ms 7768 KB Output is correct
23 Correct 21 ms 7768 KB Output is correct
24 Correct 198 ms 306624 KB Output is correct
25 Correct 214 ms 306580 KB Output is correct
26 Correct 193 ms 306536 KB Output is correct
27 Correct 53 ms 24172 KB Output is correct
28 Correct 119 ms 55512 KB Output is correct
29 Correct 65 ms 15176 KB Output is correct