Submission #1162361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162361		asdasdqwer	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	541 ms	430308 KiB

selling_rna

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

#define pii array<int,2>

struct Node {
    vector<int> cld = vector<int>(26, -1);
    pii inv;
    int startThis = -1;
    int cntEnd=0;
};

struct Node2 {
    vector<int> cld=vector<int>(26, -1);
    vector<int> tourIdx;
};

Node root;
vector<Node> trie = {root};

Node2 root2;
vector<Node2> trie2 = {root2};

void insert(string &s) {
    int idx = 0;
    for (int i=0;i<(int)s.size();i++) {
        // cout<<i<<endl;
        int cc = (s[i]-'A');
        // cout<<cc<<endl;
        if (trie[idx].cld[s[i]-'A'] == -1) {
            Node n1;
            trie[idx].cld[s[i]-'A'] = (int)trie.size();
            trie.push_back(n1);
        }
        // cout<<"here"<<endl;
        idx = trie[idx].cld[s[i]-'A'];
    }
    trie[idx].cntEnd++;
}

void insert2(string &t, int order) {
    int idx = 0;
    trie2[idx].tourIdx.push_back(order);
    for (int i=(int)t.size()-1;i>=0;i--) {
        if (trie2[idx].cld[t[i]-'A'] == -1) {
            Node2 n1;
            trie2[idx].cld[t[i]-'A'] = (int)trie2.size();
            trie2.push_back(n1);
        }
        idx = trie2[idx].cld[t[i]-'A'];
        trie2[idx].tourIdx.push_back(order);
    }
}

int counter = 0;
string tt;
void trav(int idx) {
    trie[idx].inv[0] = counter;
    if (trie[idx].cntEnd) {
        trie[idx].startThis = counter;
        for (int i=trie[idx].startThis;i<trie[idx].startThis+trie[idx].cntEnd;i++) {
            insert2(tt, i);
        }
    }

    counter += trie[idx].cntEnd;

    for (int i=0;i<26;i++) {
        if (trie[idx].cld[i] != -1) {
            tt += string(1, i+'A');
            trav(trie[idx].cld[i]);
            tt.pop_back();
        }
    }
    trie[idx].inv[1] = counter-1;
}

pii search1(string &s) {
    int idx = 0;
    for (int i=0;i<(int)s.size();i++) {
        if (trie[idx].cld[s[i]-'A'] == -1) {
            return {-1, -1};
        }
        idx=trie[idx].cld[s[i]-'A'];
    }
    return trie[idx].inv;
}

int search2(string &t, pii inv) {
    int idx = 0;
    for (int i=(int)t.size()-1;i>=0;i--) {
        if (trie2[idx].cld[t[i]-'A'] == -1) return 0;
        idx = trie2[idx].cld[t[i]-'A'];
    }
    auto it=lower_bound(trie2[idx].tourIdx.begin(), trie2[idx].tourIdx.end(), inv[0]);
    if (*it > inv[1]) {
        return 0;
    }

    int pos1 = distance(trie2[idx].tourIdx.begin(), it);

    auto it2=upper_bound(trie2[idx].tourIdx.begin(), trie2[idx].tourIdx.end(), inv[1]);
    it2 = prev(it2);
    int pos2 = distance(trie2[idx].tourIdx.begin(), it2);
    return pos2-pos1+1;
}

signed main() {
    int n,m;cin>>n>>m;
    while (n--) {
        string s;cin>>s;
        // cout<<n<<endl;
        insert(s);
    }

    // cout<<"here"<<endl;
    // cout.flush();

    trav(0);

    // cout<<"here"<<endl;
    // cout.flush();

    while (m--) {
        string s,t;cin>>s>>t;
        pii inv=search1(s);
        if (inv[0]==-1) {
            cout<<0<<endl;
            continue;
        }
        cout<<search2(t,inv)<<endl;
    }
}

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