Submission #1353415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1353415		dhuyyyy	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	220 ms	296868 KiB

selling_rna

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(s) s.begin(),s.end()
#define sz(s) (int)s.size()

using namespace std;

using ll = long long;
using ii = pair<int,int>;
using aa = array<int,3>;

const int N = 2e6+5;
const int blocks = 500;
const int INF = 1e18;
const int MOD = 1e9+7;

int n, q, timer = 0, timer1 = 0;

int pre[N][5], suf[N][5];

string s[N];

vector <int> bitsuf[N], bitpre[N];

string s1, s2;

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

void addpre(string &s, int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!pre[node][val]) pre[node][val] = ++timer;
        node = pre[node][val];
        bitpre[node].push_back(i);
    }
}

void addsuf(string &s,int i){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!suf[node][val]) suf[node][val] = ++timer1;
        node = suf[node][val];
        bitsuf[node].push_back(i);
    }
}

ii getpre(string &s){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!pre[node][val]) return {-1,-1};
        node = pre[node][val];
    }
    return {bitpre[node][0],bitpre[node].back()};
}

int getsuf(string &s,int l,int r){
    int node = 0;
    for (char c : s){
        int val = get(c);
        if (!suf[node][val]) return 0;
        node = suf[node][val];
    }
    int k = upper_bound(all(bitsuf[node]),r) - bitsuf[node].begin();
    int j = lower_bound(all(bitsuf[node]),l) - bitsuf[node].begin();
    return k - j;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    #define name "main"
    if (fopen(name".inp","r")){
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    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++){
        addpre(s[i],i);
        reverse(all(s[i]));
        addsuf(s[i],i);
    }
    while (q--){
        cin >> s1 >> s2;
        ii res = getpre(s1);
        if (res.fi == -1) cout << 0 << '\n';
        else{
            reverse(all(s2));
            cout << getsuf(s2,res.fi,res.se) << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'long long int get(char)':
selling_rna.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
   34 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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