oj.uz

Submission #306886

# Submission time Handle Problem Language Result Execution time Memory
306886 2020-09-26T13:30:21 Z jungsnow Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 316 ms 148072 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 148072 KB Output is correct
2 Correct 305 ms 140908 KB Output is correct
3 Correct 138 ms 66360 KB Output is correct
4 Correct 140 ms 63800 KB Output is correct
5 Correct 260 ms 145860 KB Output is correct
6 Correct 266 ms 145872 KB Output is correct
7 Correct 67 ms 18936 KB Output is correct
8 Correct 230 ms 94248 KB Output is correct
9 Correct 201 ms 80808 KB Output is correct
10 Correct 174 ms 83496 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4984 KB Output is correct
2 Correct 25 ms 4956 KB Output is correct
3 Correct 30 ms 4984 KB Output is correct
4 Correct 24 ms 4732 KB Output is correct
5 Correct 27 ms 4864 KB Output is correct
6 Correct 34 ms 4980 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 3 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Correct 4 ms 3456 KB Output is correct
8 Correct 292 ms 148072 KB Output is correct
9 Correct 305 ms 140908 KB Output is correct
10 Correct 138 ms 66360 KB Output is correct
11 Correct 140 ms 63800 KB Output is correct
12 Correct 260 ms 145860 KB Output is correct
13 Correct 266 ms 145872 KB Output is correct
14 Correct 67 ms 18936 KB Output is correct
15 Correct 230 ms 94248 KB Output is correct
16 Correct 201 ms 80808 KB Output is correct
17 Correct 174 ms 83496 KB Output is correct
18 Correct 31 ms 4984 KB Output is correct
19 Correct 25 ms 4956 KB Output is correct
20 Correct 30 ms 4984 KB Output is correct
21 Correct 24 ms 4732 KB Output is correct
22 Correct 27 ms 4864 KB Output is correct
23 Correct 34 ms 4980 KB Output is correct
24 Correct 299 ms 123048 KB Output is correct
25 Correct 316 ms 123220 KB Output is correct
26 Correct 308 ms 123012 KB Output is correct
27 Correct 142 ms 64492 KB Output is correct
28 Correct 210 ms 34196 KB Output is correct
29 Correct 89 ms 12392 KB Output is correct