Submission #839474

#	Time	Username	Problem	Language	Result	Execution time	Memory
839474		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	254 ms	232056 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair <int,int> pii;
int n,m;
struct trie{
    int cv(char x){
        if (x == 'A')return 0;
        if (x == 'G')return 1;
        if (x == 'C')return 2;
        return 3;
    }
    struct node{
        node* c[4];
        int in,out;
    };

    node* new_node(){
        node* res = new node;
        for (int i = 0;i < 4;i ++)res -> c[i] = nullptr;
        res -> in = 0;
        res -> out = 0;
        return res;
    }
    node* root = new_node();
    void ins(string s){
        node* cur = root;
        for (int i = 0;i < s.size();i ++){
            if (cur -> c[cv(s[i])] == nullptr){
                cur -> c[cv(s[i])] = new_node();
            }
            cur = cur -> c[cv(s[i])];
        }
    }
    pii ask(string s){
        node* cur = root;
        for (int i = 0;i < s.size();i ++){
            if (cur -> c[cv(s[i])] == nullptr){
                return {-1,-1};
            }
            cur = cur -> c[cv(s[i])];
        }
        return {cur->in,cur->out};
    }
    int timeDFS = 0;
    void dfs(node* cur){
        cur -> in = ++timeDFS;
        for (int i = 0;i < 4;i++){
            if (cur -> c[i] != nullptr)dfs(cur->c[i]);
        }
        cur -> out = timeDFS;
    }
};
trie a,rev_a;
string s[100100];
string rev_s[100100];
string p[100100],q[100100];
const int MAXSZ = 2e6;
vector <int> g[2000100];
struct query{
    int l,r,id;
};
vector <query> all[2000100];
int BIT[MAXSZ + 100];
int ans[100100];
void upd(int x){
    for (;x <= MAXSZ;x += x & -x){
        BIT[x]++;
    }
}
int get(int x){
    int res = 0;
    for (;x>0;x-=x&-x){
        res += BIT[x];
    }
    return res;
}
int ask(int l,int r){
    return get(r) - get(l-1);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (int i = 1;i <= n;i ++){
        cin>>s[i];
        a.ins(s[i]);
        rev_s[i] = s[i];
        reverse(rev_s[i].begin(),rev_s[i].end());
        rev_a.ins(rev_s[i]);
    }
    a.dfs(a.root);
    rev_a.dfs(rev_a.root);
    for (int i = 1;i <= n;i ++){
        //cout<<a.ask(s[i]).fi<<' '<<rev_a.ask(rev_s[i]).fi<<'\n';
        g[a.ask(s[i]).fi].push_back(rev_a.ask(rev_s[i]).fi);
    }
    for (int i = 1;i <= m;i ++){
        cin>>p[i]>>q[i];
        pii x = a.ask(p[i]);
        reverse(q[i].begin(),q[i].end());
        pii y = rev_a.ask(q[i]);
        //cout<<x.fi<<' '<<x.se<<' '<<y.fi<<' '<<y.se<<'\n';
        if (x.fi != -1 && y.fi != -1){
            all[x.second].push_back({y.first,y.second,i});
            all[x.first - 1].push_back({y.first,y.second,-i});
        }
    }
    for (int i = 1;i <= MAXSZ;i ++){
        for (auto x:g[i]){
            upd(x);
        }
        for (auto x:all[i]){
            if (x.id < 0){
                ans[-x.id] -= ask(x.l,x.r);
            }
            else{
                ans[x.id] += ask(x.l,x.r);
            }
        }
    }
    for (int i = 1;i <= m;i ++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie::ins(std::string)':
selling_rna.cpp:29:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for (int i = 0;i < s.size();i ++){
      |                        ~~^~~~~~~~~~
selling_rna.cpp: In member function 'pii trie::ask(std::string)':
selling_rna.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int i = 0;i < s.size();i ++){
      |                        ~~^~~~~~~~~~

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