Submission #306886

#	Time	Username	Problem	Language	Result	Execution time	Memory
306886		jungsnow	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	316 ms	148072 KiB

selling_rna

#include<bits/stdc++.h>
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int N = 100100;
const int K = 4;

struct node {
    int next[K];
    int l, r;

    node() {
        fill(begin(next), end(next), -1);
        l = N; r = -1;
    }
};

vector <node> trie(1);

struct rnode {
    int next[K];
    vector <int> a;

    rnode() {
        fill(begin(next), end(next), -1);
    }
};

vector <rnode> rtrie(1);

int num(char a) {
    if (a == 'A') return 0;
    if (a == 'G') return 1;
    if (a == 'C') return 2;
    if (a == 'U') return 3;
}

void add(int id, string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = num(ch);
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        trie[v].l = min(trie[v].l, id);
        trie[v].r = max(trie[v].r, id);
        v = trie[v].next[c];
    }
    trie[v].l = min(trie[v].l, id);
    trie[v].r = max(trie[v].r, id);
}

void radd(int id, string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = num(ch);
        if (rtrie[v].next[c] == -1) {
            rtrie[v].next[c] = rtrie.size();
            rtrie.emplace_back();
        }
        rtrie[v].a.push_back(id);
        v = rtrie[v].next[c];
    }
    rtrie[v].a.push_back(id);
}

int n, m;
string s[N], p, q;

void solve() {
    cin >> p >> q;
    int v = 0, l, r;
    for (char ch : p) {
        int c = num(ch);
        if (trie[v].next[c] == -1) {
            cout << 0 << '\n';
            return;
        }
        v = trie[v].next[c];
    }
    l = trie[v].l, r = trie[v].r;
    v = 0;
    reverse(q.begin(), q.end());
    for (char ch : q) {
        int c = num(ch);
        if (rtrie[v].next[c] == -1) {
            cout << 0 << '\n';
            return;
        }
        v = rtrie[v].next[c];
    }
    auto it = lower_bound(rtrie[v].a.begin(), rtrie[v].a.end(), l);
    l = it - rtrie[v].a.begin();
    it = upper_bound(rtrie[v].a.begin(), rtrie[v].a.end(), r);
    r = it - rtrie[v].a.begin();
    cout << r - l << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("cc.inp", "r", stdin);
//    freopen("cc.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> s[i];
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i) {
        string tm = s[i];
        add(i, tm);
        reverse(tm.begin(), tm.end());
        radd(i, tm);
    }
    while (m--) solve();
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int num(char)':
selling_rna.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
   37 | }
      | ^

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