Submission #1064948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064948		YassirSalama	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	274 ms	197836 KiB

selling_rna

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

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