oj.uz

Submission #1042967

# Submission time Handle Problem Language Result Execution time Memory
1042967 2024-08-03T16:07:43 Z khanhtb Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 160 ms 148820 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define pf push_front
#define vi vector<ll>
#define vii vector<vi>
#define pll pair<ll, ll>
#define vpll vector<pll>
#define all(a) a.begin(), a.end()
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7; 
const ll inf = 2e18;
const ll blocksz = 320;
const ll N = 2e6+8;
int n, q, trie[2][N][4], node[2], l[N], r[N];
string x, y, s[100008];
vector <int> pos[N];
 
int idx(char x){
    if (x == 'A') return(0);
    else if (x == 'C') return(1);
    else if (x == 'G') return(2);
    else return(3);
}

void add_string(string s, int id){
    for (int j = 0; j <= 1; j++){
        int u = 0;
        for (char i : s){
            if (!trie[j][u][idx(i)]) trie[j][u][idx(i)] = ++node[j];
            u = trie[j][u][idx(i)];
            if (j == 0)
            {
                if (!l[u]) l[u] = id;
                r[u] = id;
            }
            else pos[u].pb(id);
        }
        if (j == 0) reverse(all(s));
    }
}

int find_string(string x, string y){
    int u = 0;
    for (char i : x){
        if (!trie[0][u][idx(i)]) return(0);
        u = trie[0][u][idx(i)];
    }
    int L = l[u], R = r[u];
    u = 0;
    reverse(y.begin(), y.end());
    for (char i : y){
        if (!trie[1][u][idx(i)]) return(0);
        u = trie[1][u][idx(i)];
    }
    return(upper_bound(pos[u].begin(), pos[u].end(), R) - lower_bound(pos[u].begin(), pos[u].end(), L));
}
 
void solve(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) add_string(s[i], i);
    while (q--){
        cin >> x >> y;
        cout << find_string(x, y) << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }   
    ll T = 1;
    // cin >> T;
    for (ll i = 1; i <= T; i++) {
        solve();
        cout << '\n';
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50512 KB Output is correct
2 Correct 25 ms 50524 KB Output is correct
3 Correct 23 ms 50524 KB Output is correct
4 Correct 23 ms 50440 KB Output is correct
5 Correct 21 ms 50548 KB Output is correct
6 Correct 27 ms 50520 KB Output is correct
7 Correct 26 ms 50520 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 148820 KB Output is correct
2 Correct 136 ms 144008 KB Output is correct
3 Correct 73 ms 113332 KB Output is correct
4 Correct 75 ms 110756 KB Output is correct
5 Correct 111 ms 140080 KB Output is correct
6 Correct 113 ms 141452 KB Output is correct
7 Correct 53 ms 65872 KB Output is correct
8 Correct 111 ms 114500 KB Output is correct
9 Correct 95 ms 106064 KB Output is correct
10 Correct 83 ms 102484 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51792 KB Output is correct
2 Correct 34 ms 51536 KB Output is correct
3 Correct 37 ms 51792 KB Output is correct
4 Correct 32 ms 51644 KB Output is correct
5 Correct 34 ms 51676 KB Output is correct
6 Correct 37 ms 51548 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50512 KB Output is correct
2 Correct 25 ms 50524 KB Output is correct
3 Correct 23 ms 50524 KB Output is correct
4 Correct 23 ms 50440 KB Output is correct
5 Correct 21 ms 50548 KB Output is correct
6 Correct 27 ms 50520 KB Output is correct
7 Correct 26 ms 50520 KB Output is correct
8 Correct 145 ms 148820 KB Output is correct
9 Correct 136 ms 144008 KB Output is correct
10 Correct 73 ms 113332 KB Output is correct
11 Correct 75 ms 110756 KB Output is correct
12 Correct 111 ms 140080 KB Output is correct
13 Correct 113 ms 141452 KB Output is correct
14 Correct 53 ms 65872 KB Output is correct
15 Correct 111 ms 114500 KB Output is correct
16 Correct 95 ms 106064 KB Output is correct
17 Correct 83 ms 102484 KB Output is correct
18 Correct 36 ms 51792 KB Output is correct
19 Correct 34 ms 51536 KB Output is correct
20 Correct 37 ms 51792 KB Output is correct
21 Correct 32 ms 51644 KB Output is correct
22 Correct 34 ms 51676 KB Output is correct
23 Correct 37 ms 51548 KB Output is correct
24 Correct 130 ms 132432 KB Output is correct
25 Correct 160 ms 132628 KB Output is correct
26 Correct 159 ms 131384 KB Output is correct
27 Correct 76 ms 104392 KB Output is correct
28 Correct 113 ms 75864 KB Output is correct
29 Correct 80 ms 58944 KB Output is correct