oj.uz

Submission #948465

# Submission time Handle Problem Language Result Execution time Memory
948465 2024-03-18T06:35:47 Z tminh_hk20 Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 507 ms 1048576 KB 
#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

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.0 / 10.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 507 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14600 KB Output is correct
2 Correct 26 ms 15360 KB Output is correct
3 Correct 31 ms 14804 KB Output is correct
4 Correct 29 ms 13880 KB Output is correct
5 Correct 34 ms 14320 KB Output is correct
6 Correct 34 ms 14396 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 3 ms 9820 KB Output is correct
6 Correct 3 ms 9972 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Runtime error 507 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -