Submission #294179

#	Time	Username	Problem	Language	Result	Execution time	Memory
294179		b00n0rp	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	597 ms	588920 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(),v.end()

int n,q;

string s[200005];

struct node{
    vi pos;
    int to[26];
} trie1[2000005],trie2[2000005];

int SZ1 = 1,SZ2 = 1;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;
    REP(i,n) cin >> s[i];
    sort(s,s+n);
    REP(i,n){
        int cur = 1;
        REP(j,(int)s[i].length()){
            int let = s[i][j]-'A';
            if(!trie1[cur].to[let]) trie1[cur].to[let] = ++SZ1; 
            cur = trie1[cur].to[let];
            trie1[cur].pos.pb(i);
        }
        cur = 1;
        FORD(j,(int)s[i].length()-1,0){
            // cout << i << " " << j << endl;
            int let = s[i][j]-'A';
            if(!trie2[cur].to[let]) trie2[cur].to[let] = ++SZ2; 
            cur = trie2[cur].to[let];
            trie2[cur].pos.pb(i);
        }
    }
    REP(i,SZ2+1) sort(all(trie2[i].pos));
    REP(i,q){
        string s1,s2; cin >> s1 >> s2;
        int cur1 = 1,cur2 = 1;
        bool f = 0;
        REP(j,(int)s1.length()){
            int let = s1[j]-'A';
            if(!trie1[cur1].to[let]){
                f = 1;
                break;
            } 
            cur1 = trie1[cur1].to[let];
        }
        if(f){
            cout << "0\n";
            continue;
        }
        FORD(j,(int)s2.length()-1,0){
            int let = s2[j]-'A';
            if(!trie2[cur2].to[let]){
                f = 1;
                break;
            } 
            cur2 = trie2[cur2].to[let];
        }
        if(f){
            cout << "0\n";
            continue;
        }
        // cout << "-------------------------------\n";
        // cout << s1 << " - " << s2 << endl;
        // cout << trie1[cur1].pos.size() << endl;
        // for(auto x:trie1[cur1].pos) cout << x << " "; 
        // cout << endl;
        // cout << trie2[cur2].pos.size() << endl;
        // for(auto x:trie2[cur2].pos) cout << x << " "; 
        // cout << endl;
        // cout << "-------------------------------\n";
        cout << upper_bound(all(trie2[cur2].pos),trie1[cur1].pos.back())-lower_bound(all(trie2[cur2].pos),trie1[cur1].pos[0]) << "\n";
    }
}

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