Submission #1280846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280846		courte_.sanma	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	324 ms	314616 KiB

selling_rna

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e6+6;
int n,q;
string s[N];
struct trie {
    struct Node {
        vector<int> v;
        int child[4];
        int l,r;
        void init() {
            memset(child,-1,sizeof(child));
            l=2e9, r=0;
        }
    } 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 type) {
        int p=0;
        for (char c:s) {
            int &nxt=node[p].child[c-'0'];
            if (nxt==-1) {
                nxt=new_node();
            }
            p=nxt;
            if (type==2) node[p].v.push_back(id);
            else { node[p].l=min(node[p].l,id); node[p].r=max(node[p].r,id); }
        }
    }
    pii get1(string s) {
        int p=0;
        for (char c:s) {
            p=node[p].child[c-'0'];
            if (p==-1) return {-1,-1};
        }
        return make_pair(node[p].l,node[p].r);
    }
    vector<int> get2(string s) {
        int p=0;
        for (char c:s) {
            p=node[p].child[c-'0'];
            if (p==-1) return {};
        }
        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]);
    }
    sort(s+1,s+1+n);
    for (int i=1; i<=n; ++i) {
        t1.add(s[i],i,1);
        reverse(s[i].begin(),s[i].end());
        t2.add(s[i],i,2);
    }
    for (int i=0; i<=t2.cur; ++i) sort(t2.node[i].v.begin(),t2.node[i].v.end());
    while (q--) {
        string s1,s2;
        cin>>s1>>s2;
        reverse(s2.begin(),s2.end());
        compress(s1); compress(s2);
        pii range=t1.get1(s1);
        vector<int> a=t2.get2(s2);
        if (range.fi==-1 || a.size()==0) { cout<<0<<'\n'; continue; }
        int l=lower_bound(a.begin(),a.end(),range.fi)-a.begin();
        int r=upper_bound(a.begin(),a.end(),range.se)-a.begin(); if (r==0) { cout<<0<<'\n'; continue; }
        cout<<r-l<<'\n';
    }
    return 0;
}

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