Submission #1280838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280838		courte_.sanma	Selling RNA Strands (JOI16_selling_rna)	C++20	0 / 100	1601 ms	294788 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+6;
int n,q;
string s[N];
struct trie {
    struct Node {
        vector<int> v;
        int child[4];
        void init() {
            memset(child,-1,sizeof(child));
        }
    } node[N];
    int cur;
    trie() {
        cur=0;
        node[cur].init();
    }
    int new_node() {
        ++cur;
        node[cur].init();
        return cur;
    }
    void add(string s, int id) {
        int p=0;
        for (char c:s) {
            int &nxt=node[p].child[c-'0'];
            if (nxt==-1) {
                nxt=new_node();
            }
            p=nxt;
            node[p].v.push_back(id);
        }
    }
    vector<int> get(string s) {
        int p=0;
        for (char c:s) {
            p=node[p].child[c-'0'];
        }
        return node[p].v;
    }
} t1,t2;
void compress(string &s) {
    for (int i=0; i<s.length(); ++i) {
        if (s[i]=='A') s[i]='0';
        if (s[i]=='G') s[i]='1';
        if (s[i]=='U') s[i]='2';
        if (s[i]=='C') s[i]='3';
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    for (int i=1; i<=n; ++i) {
        cin>>s[i];
        compress(s[i]);
    }
    for (int i=1; i<=n; ++i) {
        t1.add(s[i],i);
        reverse(s[i].begin(),s[i].end());
        t2.add(s[i],i);
    }
    while (q--) {
        string l,r;
        cin>>l>>r;
        compress(l); compress(r);
        vector<int> a=t1.get(l);
        vector<int> b=t2.get(r);
        int i=0, j=0;
        int res=0;
        for (int i=0; i<a.size(); ++i) {
            while (j<b.size() && b[j]<a[i]) ++j;
            if (b[j]==a[i]) ++res;
        }
        cout<<res<<'\n';
    }
    return 0;
}

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