Submission #1277348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277348		khoavn2008	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	647 ms	990628 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld double
#define FOR(i,l,r) for(ll i = (l), _r = (r); i <= _r; i++)
#define FORNG(i,r,l) for(ll i = (r), _l = (l); i >= _l; i--)
#define REP(i,r) for(ll i = 0, _r = (r); i <= _r; i++)
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define size(v) ((ll)(v).size())
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)

const ll MOD = 1e9 + 7, N = 1e5 + 10, INF = 1e9, LOG = 21;
const ll MAXNODE = 4e6 + 10, W = 26;
struct Node{
    Node *child[W];
    vector<ll> vec;
    Node(){
        memset(child, 0, sizeof child);
    }
}T[MAXNODE];
ll cntUsedNode = 0;
Node *NEW(){return &T[++cntUsedNode];}
struct TRIE{
    Node *root = NEW();
    void addStr(string &s,ll idx){
        Node *p = root;
        for(char c : s){
            if(!p->child[c - 'A'])p->child[c - 'A'] = NEW();
            p = p->child[c - 'A'];
            p->vec.pb(idx);
        }
    }
    pair<ll,ll> getRange(string &prefix){
        Node *p = root;
        for(char c : prefix){
            if(!p->child[c - 'A'])return {-1, -1};
            p = p->child[c - 'A'];
        }
        return {p->vec.front(), p->vec.back()};
    }
    ll query(string &sufix,ll l,ll r){
        Node *p = root;
        for(char c : sufix){
            if(!p->child[c - 'A'])return 0;
            p = p->child[c - 'A'];
        }
        return upper_bound(all(p->vec), r) - lower_bound(all(p->vec), l);
    }
}Trie,revTrie;
ll n,q;
string s[N];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    FOR(i,1,n)cin>>s[i];
    sort(s + 1, s + 1 + n);
    FOR(i,1,n){
        Trie.addStr(s[i], i);
        reverse(all(s[i]));
        revTrie.addStr(s[i], i);
    }
    while(q--){
        string p,q;cin>>p>>q;
        auto [l, r] = Trie.getRange(p);
        if(l == -1){
            cout<<0<<endl;
            continue;
        }
        reverse(all(q));
        cout<<revTrie.query(q, l, r)<<endl;
    }
}

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