oj.uz

Submission #1064948

# Submission time Handle Problem Language Result Execution time Memory
1064948 2024-08-18T19:56:46 Z YassirSalama Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 274 ms 197836 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
int get(char c){
    if(c=='A') return 0;
    if(c=='G') return 1;
    if(c=='C') return 2;
    if(c=='U') return 3;
    return 5;
}
struct Trie1{
    struct Node{
        Node* c[4];
        int l=1e18;
        int r=-1e18;
        Node() {
            for(int i=0;i<4;i++) c[i]=nullptr;
        }
    };
    Node* root=new Node();
    void insert(string s,int id){
        int n=s.length();
        Node* node=root;
        for(int i=0;i<n;i++){
            if(node->c[get(s[i])]==nullptr){
                node->c[get(s[i])]=new Node();
            }
            node=node->c[get(s[i])];
            node->l=min(node->l,id); 
            node->r=max(node->r,id);
        }
    }
    pair<int,int> query(string s){
        int n=s.length();
        Node* node=root;
        for(int i=0;i<n;i++){
            if(node->c[get(s[i])]==nullptr) return {-1,-1};
            node=node->c[get(s[i])];
        }
        return {node->l,node->r};
    }
};
struct Trie2{
    struct Node{
        Node* c[4];
        vector<int> ids;
        Node() {
            for(int i=0;i<4;i++) c[i]=nullptr;
        }
    };
    Node* root=new Node();
    void insert(string s,int id){
        int n=s.length();
        Node* node=root;
        for(int i=n-1;i>=0;i--){
            if(node->c[get(s[i])]==nullptr){
                node->c[get(s[i])]=new Node();
            }
            node=node->c[get(s[i])];
            node->ids.push_back(id);
        }
    }
    int query(string s,pair<int,int> lf){
        int n=s.length();
        int ans=0;
        Node* node=root;
        for(int i=s.length()-1;i>=0;i--){
            if(node->c[get(s[i])]==nullptr) return 0;
            node=node->c[get(s[i])];
        }
        int l=lower_bound(all(node->ids),lf.F)-node->ids.begin();
        int r=upper_bound(all(node->ids),lf.S)-node->ids.begin();
        return r-l;
    }
};

signed main(){
    int n;
    cin>>n;
    int m;
    cin>>m;
    vector<string> s;
    for(int i=0;i<n;i++){
        string t;
        cin>>t;
        s.pb(t);
    }
    sort(all(s));
    Trie1 t1;
    Trie2 t2;
    for(int i=0;i<n;i++){
        t1.insert(s[i],i);
        t2.insert(s[i],i);
    }
    for(int i=0;i<m;i++){
        string a,b;
        cin>>a>>b;
        pair<int,int> aa=t1.query(a);
        cout<<t2.query(b,aa)<<endl;
    }
}

Compilation message

selling_rna.cpp: In member function 'long long int Trie2::query(std::string, std::pair<long long int, long long int>)':
selling_rna.cpp:68:13: warning: unused variable 'n' [-Wunused-variable]
   68 |         int n=s.length();
      |             ^
selling_rna.cpp:69:13: warning: unused variable 'ans' [-Wunused-variable]
   69 |         int ans=0;
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 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 251 ms 191252 KB Output is correct
2 Correct 234 ms 181712 KB Output is correct
3 Correct 182 ms 148560 KB Output is correct
4 Correct 180 ms 141772 KB Output is correct
5 Correct 206 ms 194992 KB Output is correct
6 Correct 197 ms 197836 KB Output is correct
7 Correct 123 ms 23232 KB Output is correct
8 Correct 210 ms 132608 KB Output is correct
9 Correct 196 ms 114636 KB Output is correct
10 Correct 134 ms 109516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 4132 KB Output is correct
2 Correct 50 ms 3268 KB Output is correct
3 Correct 67 ms 3516 KB Output is correct
4 Correct 51 ms 3004 KB Output is correct
5 Correct 49 ms 3024 KB Output is correct
6 Correct 63 ms 3404 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 251 ms 191252 KB Output is correct
9 Correct 234 ms 181712 KB Output is correct
10 Correct 182 ms 148560 KB Output is correct
11 Correct 180 ms 141772 KB Output is correct
12 Correct 206 ms 194992 KB Output is correct
13 Correct 197 ms 197836 KB Output is correct
14 Correct 123 ms 23232 KB Output is correct
15 Correct 210 ms 132608 KB Output is correct
16 Correct 196 ms 114636 KB Output is correct
17 Correct 134 ms 109516 KB Output is correct
18 Correct 74 ms 4132 KB Output is correct
19 Correct 50 ms 3268 KB Output is correct
20 Correct 67 ms 3516 KB Output is correct
21 Correct 51 ms 3004 KB Output is correct
22 Correct 49 ms 3024 KB Output is correct
23 Correct 63 ms 3404 KB Output is correct
24 Correct 239 ms 159432 KB Output is correct
25 Correct 271 ms 159688 KB Output is correct
26 Correct 223 ms 157424 KB Output is correct
27 Correct 183 ms 124288 KB Output is correct
28 Correct 274 ms 48568 KB Output is correct
29 Correct 191 ms 16824 KB Output is correct