Submission #1070097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070097		giaminh2211	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	214 ms	320660 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40