Submission #423089

#	Time	Username	Problem	Language	Result	Execution time	Memory
423089		doowey	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	403 ms	238360 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const int L = (int)2e6 + 100;

vector<int> LEF[L];
vector<int> RIG[L];
int lef[L][4];
int rig[L][4];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    for(int i = 0 ; i < L; i ++ ){
        for(int j = 0 ; j < 4; j ++ ){
            lef[i][j]=-1;
            rig[i][j]=-1;
        }
    }
    int ca = 0, cb = 0;
    int n, m;
    cin >> n >> m;
    string ss[n];
    for(int i = 0 ; i < n; i ++ ){
        cin >> ss[i];
    }
    sort(ss, ss + n);
    string s;
    int cur;
    map<char, int> match;
    match['A'] = 0;
    match['G'] = 1;
    match['C'] = 2;
    match['U'] = 3;
    int id;
    for(int i = 0; i < n; i ++ ){
        s = ss[i];
        cur = 0;
        for(auto x : s){
            id = match[x];
            if(lef[cur][id] == -1){
                ca ++ ;
                lef[cur][id] = ca;
            }
            cur = lef[cur][id];
            LEF[cur].push_back(i);
        }
        cur = 0;
        for(int j = s.size() - 1; j >= 0 ; j -- ){
            id = match[s[j]];
            if(rig[cur][id] == -1){
                cb ++ ;
                rig[cur][id] = cb;
            }
            cur = rig[cur][id];
            RIG[cur].push_back(i);
        }
    }
    string pi, qi;
    int lli = 0, rri = 0;
    map<pii, int> res;
    int cnt;
    int low, high;
    int i1, i2;
    for(int iq = 1; iq <= m ; iq ++ ){
        cin >> pi >> qi;
        reverse(qi.begin(), qi.end());
        lli = rri = 0;
        for(auto x : pi){
            id = match[x];
            if(lef[lli][id] == -1){
                lli = -1;
                break;
            }
            lli = lef[lli][id];
        }
        for(auto x : qi){
            id = match[x];
            if(rig[rri][id] == -1){
                rri = -1;
                break;
            }
            rri = rig[rri][id];
        }
        if(lli == -1 || rri == -1){
            cout << "0\n";
            continue;
        }
        low = LEF[lli][0];
        high = LEF[lli].back();
        i1 = lower_bound(RIG[rri].begin(), RIG[rri].end(), low) - RIG[rri].begin();
        i2 = lower_bound(RIG[rri].begin(), RIG[rri].end(), high + 1) - RIG[rri].begin();
        cout << i2 - i1 << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:72:9: warning: unused variable 'cnt' [-Wunused-variable]
   72 |     int cnt;
      |         ^~~

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