oj.uz

Submission #856972

# Submission time Handle Problem Language Result Execution time Memory
856972 2023-10-05T02:58:59 Z TS_2392 Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 164 ms 205904 KB 
#include <bits/stdc++.h>

using namespace std;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a)        a.begin(), a.end()
#define lwb           lower_bound
#define upb           upper_bound
#define sz(a)         (int) a.size()
#define eb            emplace_back

const int N = 2e6 + 10;
vector <int> through[N];
int trie[2][4][N], L[N], R[N];
int n, m, trie_sz[2];
string s[N], DNA = "ACGT";
int trans(char c){
	if (c == 'A') return 0;
	if (c == 'U') return 1;
	if (c == 'G') return 2;
	if (c == 'C') return 3;
}
void add_str(string & s, int j, int t, bool r = 0){
    int v = 1;
    for (int i = 0; i < sz(s); i++){
        char u = s[r ? sz(s) - 1 - i : i];
        int c = trans(u);
        if (!trie[t][c][v]) trie[t][c][v] = trie_sz[t]++;
        v = trie[t][c][v];
        if (t == 0){
            if (L[v] == 0) L[v] = j;
            R[v] = max(R[v], j);
        }
        else through[v].eb(j);
    }
}
int query(string & s, int t, bool r = 0){
    int v = 1;
    for (int i = 0; i < sz(s); i++) {
        char u = s[r ? sz(s) - 1 - i : i];
        int c = trans(u);
        v = trie[t][c][v];
        if (!v) return 0;
    }
    return v;
}

int main(){
    SPEED;
    cin >> n >> m;
    trie_sz[0] = trie_sz[1] = 2;
    for (int i = 0; i < n; i++) cin >> s[i];
    sort(s, s + n);
    for (int i = 0; i < n; i++){
        add_str(s[i], i + 1, 0);
        add_str(s[i], i + 1, 1, 1);
    }
    for (int i = 0; i < m; i++){
        string s, t; cin >> s >> t;
        int I = query(s, 0), I2 = query(t, 1, 1);
        int p1 = lwb(all(through[I2]), L[I]) - through[I2].begin();
        int p2 = upb(all(through[I2]), R[I]) - through[I2].begin();
        cout << max(0, p2 - p1) << '\n';
    }
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 112452 KB Output is correct
2 Correct 25 ms 112220 KB Output is correct
3 Correct 24 ms 112220 KB Output is correct
4 Correct 23 ms 112220 KB Output is correct
5 Correct 25 ms 112220 KB Output is correct
6 Correct 23 ms 112220 KB Output is correct
7 Correct 23 ms 112216 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 205904 KB Output is correct
2 Correct 143 ms 205136 KB Output is correct
3 Correct 84 ms 173900 KB Output is correct
4 Correct 84 ms 171396 KB Output is correct
5 Correct 124 ms 200784 KB Output is correct
6 Correct 131 ms 202132 KB Output is correct
7 Correct 58 ms 127860 KB Output is correct
8 Correct 113 ms 162640 KB Output is correct
9 Correct 113 ms 163436 KB Output is correct
10 Correct 98 ms 159572 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 113588 KB Output is correct
2 Correct 40 ms 113232 KB Output is correct
3 Correct 39 ms 113232 KB Output is correct
4 Correct 35 ms 112912 KB Output is correct
5 Correct 39 ms 113192 KB Output is correct
6 Correct 42 ms 113492 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 112452 KB Output is correct
2 Correct 25 ms 112220 KB Output is correct
3 Correct 24 ms 112220 KB Output is correct
4 Correct 23 ms 112220 KB Output is correct
5 Correct 25 ms 112220 KB Output is correct
6 Correct 23 ms 112220 KB Output is correct
7 Correct 23 ms 112216 KB Output is correct
8 Correct 134 ms 205904 KB Output is correct
9 Correct 143 ms 205136 KB Output is correct
10 Correct 84 ms 173900 KB Output is correct
11 Correct 84 ms 171396 KB Output is correct
12 Correct 124 ms 200784 KB Output is correct
13 Correct 131 ms 202132 KB Output is correct
14 Correct 58 ms 127860 KB Output is correct
15 Correct 113 ms 162640 KB Output is correct
16 Correct 113 ms 163436 KB Output is correct
17 Correct 98 ms 159572 KB Output is correct
18 Correct 44 ms 113588 KB Output is correct
19 Correct 40 ms 113232 KB Output is correct
20 Correct 39 ms 113232 KB Output is correct
21 Correct 35 ms 112912 KB Output is correct
22 Correct 39 ms 113192 KB Output is correct
23 Correct 42 ms 113492 KB Output is correct
24 Correct 152 ms 194196 KB Output is correct
25 Correct 164 ms 194372 KB Output is correct
26 Correct 139 ms 193108 KB Output is correct
27 Correct 80 ms 164944 KB Output is correct
28 Correct 153 ms 137900 KB Output is correct
29 Correct 74 ms 120944 KB Output is correct