Submission #423037

#	Time	Username	Problem	Language	Result	Execution time	Memory
423037		doowey	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1505 ms	647140 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;

unordered_set<int> LEF[L];
unordered_set<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 s;
    int cur;
    map<char, int> match;
    match['A'] = 0;
    match['G'] = 1;
    match['C'] = 2;
    match['U'] = 3;
    int id;
    for(int i = 1; i <= n; i ++ ){
        cin >> s;
        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].insert(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].insert(i);
        }
    }
    string pi, qi;
    int lli = 0, rri = 0;
    map<pii, int> res;
    int cnt;
    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;
        }
        if(res.count(mp(lli, rri))){
            cout << res[mp(lli,rri)] << "\n";
        }
        else{
            cnt = 0;
            if(LEF[lli].size() <= RIG[rri].size()){
                for(auto x : LEF[lli]){
                    if(RIG[rri].count(x)){
                        cnt ++ ;
                    }
                }
            }
            else{
                for(auto x : RIG[rri]){
                    if(LEF[lli].count(x)){
                        cnt ++ ;
                    }
                }
            }
            res[mp(lli,rri)] = cnt;
            cout << cnt << "\n";
        }
    }
    return 0;
}

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