제출 #710647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710647		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	520 ms	231892 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

#define tcT template<class T
#define each(e, a) for(auto &(e) : (a))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)(v).size()
#define nl '\n';

using ll = long long;
tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b, 1 : 0; }
tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b, 1 : 0; }

const ll INF = 1e18; const int MOD = 1e9 + 7;

const int MX = 1e5+5;

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

char get_char(char c) {
    if(c == 0) return 'A';
    else if(c == 1) return 'C';
    else if(c == 2) return 'G';
    return 'U';
}

struct Trie {
    vector<array<int,4>> nex = {{{}}};
    vector<vector<int>> lst = {{}};
    vector<int> cnt = {0};
    void ins(const string&s, int ind) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            char c = getid(s[i]);
            if(!nex[cur][c]) {
                nex[cur][c] = sz(nex);
                nex.push_back({{{}}});
                lst.push_back({});
                cnt.push_back(0);
            }
            cur = nex[cur][c];
            lst[cur].push_back(ind);
        }
        cnt[cur]++;
    }
    void dfs(int u, string&cur, vector<string>& anslst) {
        for(int i = 0; i < cnt[u]; i++) {
            anslst.push_back(cur);
        }

        for(int i = 0; i < 4; i++) {
            if(nex[u][i]) {
                cur += get_char(i);
                dfs(nex[u][i], cur, anslst);
                cur.pop_back();
            }
        }
    }

    pair<int,int> getlr(const string&s) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            int c = getid(s[i]);
            if(!nex[cur][c]) return {-1, -1};
            cur = nex[cur][c];
        }
        return {*lst[cur].begin(), *lst[cur].rbegin()};
    }

    int get_cnt(const string&s, int l, int r) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            int c = getid(s[i]);
            if(!nex[cur][c]) return 0;
            cur = nex[cur][c];
        }
        return upper_bound(all(lst[cur]), r) - lower_bound(all(lst[cur]), l);
    }
};

int N, M;
string s[MX];

void sort_all() {
    Trie trie;
    for(int i = 0; i < N; i++) {
        trie.ins(s[i], i);
    }
    vector<string> lst;
    string cur = "";
    trie.dfs(0, cur, lst);
    for(int i = 0; i < N; i++) s[i] = lst[i];
}



void solve() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> s[i];
    }
    sort_all();

    Trie trie1;
    for(int i = 0; i < N; i++) {
        trie1.ins(s[i], i);
        reverse(all(s[i]));
    }

    Trie trie2;
    for(int i = 0; i < N; i++) {
        trie2.ins(s[i], i);
    }

    while(M-- > 0) {
        string P, Q;
        cin >> P >> Q;
        reverse(all(Q));
        int l, r; tie(l, r) = trie1.getlr(P);
        if(~l) { cout << trie2.get_cnt(Q, l, r) << nl; }
        else cout << "0\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();

    return 0;
}

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