Submission #948465

#	Time	Username	Problem	Language	Result	Execution time	Memory
948465		tminh_hk20	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	507 ms	1048576 KiB

selling_rna

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define int long long
#define ii pair<int,int>
#define getbit(x,y) (x>>y &1)
#define turnon(x,y) (x | (1<<y))
#define turnoff(x,y) (x ^ (1<<y))
#define Task "rna"

using namespace std;
const int N = 1e5;
const int MOD = 1e9+7;
const int MOD2 =  1e9+2277;
const int MOD3 = 1e9+9;
const int base = 311;
const int BSIZE = 320;

int n, m;
string si[N+10];
pair<string, string> qu[N+10];

namespace subfull{
    int cv[255], ct=0;
    string s, t;

    struct node{
        int child[5];
        vector<string> v;
    };

    vector<node> trie;


    void newnode(){
        node a;
        memset(a.child,0,sizeof(a.child));
        trie.push_back(a);
    }

    void uptrie(string &s){
        int k = 0;
        for (int i=s.size()-1;i>=0;i--){
            int a = cv[s[i]];
            if (!trie[k].child[a]){
                newnode();
                trie[k].child[a] = ++ct;
            }
            k = trie[k].child[a];
            trie[k].v.push_back(s);
        }
    }

    int get(string &s, string &t){
        int k = 0;
        for (int i=t.size()-1;i>=0;i--){
            int a = cv[t[i]];
            if (!trie[k].child[a]) return 0;
            k = trie[k].child[a];
        }

        int l = lower_bound(trie[k].v.begin(),trie[k].v.end(),s)-trie[k].v.begin();
        s.push_back('Z');
        int r = upper_bound(trie[k].v.begin(),trie[k].v.end(),s)-trie[k].v.begin()-1;
//        cout <<">"<<s<<" "<<s2<<" "<<l<<" "<<r<<endl;
//        for (auto p: trie[k].v) cout <<p<<" "; cout <<endl;
        return (r-l+1);
    }

    void solve(){
        newnode();
        cv['A'] =0;
        cv['G'] =1;
        cv['C'] =2;
        cv['U'] =3;

        for (int i=1;i<=n;i++){
            s = si[i];
            uptrie(s);
        }
        for (int i=0;i<=ct;i++) sort(trie[i].v.begin(),trie[i].v.end());
        for (int i=1;i<=m;i++){
            s = qu[i].fi;
            t = qu[i].se;
            cout << get(s,t)<<endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

//    freopen(Task".inp","r",stdin);
//    freopen(Task".out","w",stdout);
//
    cin>> n>> m;
    for (int i=1;i<=n;i++){
        cin>> si[i];
    }

    for (int i=1;i<=m;i++){
        cin>> qu[i].fi>>qu[i].se;
    }

    subfull::solve();

//



}

Compilation message (stderr)

selling_rna.cpp: In function 'void subfull::uptrie(std::string&)':
selling_rna.cpp:45:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |             int a = cv[s[i]];
      |                            ^
selling_rna.cpp: In function 'long long int subfull::get(std::string&, std::string&)':
selling_rna.cpp:58:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |             int a = cv[t[i]];
      |                            ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40