Submission #1280844

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

selling_rna

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

struct Node {
    int child[4];
    vector<int> ids;
    Node() { memset(child, -1, sizeof(child)); }
};

struct Trie {
    vector<Node> t;
    Trie() { t.emplace_back(); }

    void add(string &s, int id) {
        int p=0;
        for (char c:s) {
            int x=c-'0';
            if (t[p].child[x]==-1) {
                t[p].child[x]=t.size();
                t.emplace_back();
            }
            p=t[p].child[x];
            t[p].ids.push_back(id);
        }
    }

    pair<int,int> get(string &s) {
        int p=0;
        for (char c:s) {
            int x=c-'0';
            if (t[p].child[x]==-1) return {2e9,0};
            p=t[p].child[x];
        }
        return {t[p].ids.front(), t[p].ids.back()};
    }
};

void compress(string &s) {
    for (char &c:s) {
        if (c=='A') c='0';
        else if (c=='G') c='1';
        else if (c=='U') c='2';
        else if (c=='C') c='3';
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,q; cin>>n>>q;
    vector<string> s(n+1);
    for (int i=1;i<=n;i++) cin>>s[i];

    vector<string> rev=s;
    for (int i=1;i<=n;i++) reverse(rev[i].begin(), rev[i].end());

    Trie pre,suf;
    vector<int> id(n); iota(id.begin(), id.end(), 1);

    sort(id.begin(), id.end(), [&](int a,int b){return s[a]<s[b];});
    for (int i=0;i<n;i++) {
        string x=s[id[i]];
        compress(x);
        pre.add(x,i);
    }

    sort(id.begin(), id.end(), [&](int a,int b){return rev[a]<rev[b];});
    for (int i=0;i<n;i++) {
        string x=rev[id[i]];
        compress(x);
        suf.add(x,i);
    }

    while(q--) {
        string p,q; cin>>p>>q;
        compress(p); compress(q);
        reverse(q.begin(),q.end());
        auto range1=pre.get(p);
        auto range2=suf.get(q);

        if (range1.fi>range1.se || range2.fi>range2.se) {
            cout<<0<<'\n';
            continue;
        }

        vector<int> a;
        for (int i=range2.fi;i<=range2.se;i++) a.push_back(i);
        int l=lower_bound(a.begin(),a.end(),range1.fi)-a.begin();
        int r=upper_bound(a.begin(),a.end(),range1.se)-a.begin();
        cout<<r-l<<'\n';
    }
}

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