Submission #1042967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042967		khanhtb	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	160 ms	148820 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40