Submission #1279510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279510		LmaoLmao	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	567 ms	679056 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa = array<int,3>;
const int N = 1e5+5;

string s[N];

struct TRIYEUMINHEM {
    int trie[N*20][26];
    vector<int> a[N*20];
    int timer=0;
    void add(string s,int id) {
        int u=0;
        for(char c:s) {
            int v=c-'A';
            if(!trie[u][v]) {
                trie[u][v]=++timer;
            }
            u=trie[u][v];
            a[u].push_back(id);
        }
    }
    int get(string s,int l,int r) {
        int u=0;
        for(char c:s) {
            int v=c-'A';
            if(!trie[u][v]) return 0;
            u=trie[u][v];
        }
        int x=lower_bound(a[u].begin(),a[u].end(),l)-a[u].begin();
        int y=upper_bound(a[u].begin(),a[u].end(),r)-a[u].begin();
        return y-x;
    }
    ii getlr(string s) {
        int u=0;
        for(char c:s) {
            int v=c-'A';
            if(!trie[u][v]) return {-1,-1};
            u=trie[u][v];
        }
        return {*a[u].begin(),*a[u].rbegin()};
    }
} rev,trie;

int bs(string s) {

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) {
        cin >> s[i];
    }
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++) {
        reverse(s[i].begin(),s[i].end());
        rev.add(s[i],i);
        reverse(s[i].begin(),s[i].end());
        trie.add(s[i],i);
    }
    while(q--) {
        string pre,suf;
        cin >> pre >> suf;
        reverse(suf.begin(),suf.end());
        ii res=trie.getlr(pre);
        if(res.fi==-1) cout << 0 << endl;
        else {

            cout << rev.get(suf,res.fi,res.se) << endl;
        }
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'long long int bs(std::string)':
selling_rna.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
   53 | }
      | ^

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