제출 #1361791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361791		nguyenkhangninh99	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	167 ms	189308 KiB

selling_rna

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

int get_val(char f) {
    if (f == 'A') return 0;
    if (f == 'G') return 1;
    if (f == 'C') return 2;
    return 3;
}

const int maxn = 2e6 + 5, INF = 1e9;
struct Trie{
    struct Node{
        int child[4], l, r;
    } nodes[maxn];

    int cur;
    Trie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].l = INF; nodes[0].r = -INF;
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].l = INF; nodes[cur].r = -INF;
        return cur;
    }

    void add_string(string s, int id) {
        int pos = 0;
        for(char f: s){
            int c = get_val(f);
            if(nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
            pos = nodes[pos].child[c];

            nodes[pos].l = min(nodes[pos].l, id);
            nodes[pos].r = max(nodes[pos].r, id);
        }
    }
    pair<int, int> get_range(string s) {
        int pos = 0;
        for (char f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) return {-1, -1};
            pos = nodes[pos].child[c];
        }
        return {nodes[pos].l, nodes[pos].r};
    }
};

struct ReversedTrie{
    struct Node{
        int child[4];
        vector<int> ids;
    } nodes[maxn];

    int cur;
    ReversedTrie() : cur(0) {
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
    };

    int new_node() {
        cur++;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        return cur;
    }

    void add_string(string s, int id) {
        reverse(s.begin(), s.end());
        int pos = 0;
        for(char f: s){
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) nodes[pos].child[c] = new_node();
            pos = nodes[pos].child[c];
            nodes[pos].ids.push_back(id);
        }
    }

    int query(string s, pair<int, int> range) {
        reverse(s.begin(), s.end());
        int pos = 0;
        for (auto f : s) {
            int c = get_val(f);
            if (nodes[pos].child[c] == -1) return 0;
            pos = nodes[pos].child[c];
        }

        int l = lower_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.first) - nodes[pos].ids.begin();
        int r = upper_bound(nodes[pos].ids.begin(), nodes[pos].ids.end(), range.second) - nodes[pos].ids.begin() - 1;

        return r - l + 1;
    }
};
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;

    vector<string> v;
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());

    Trie trie1;
    ReversedTrie trie2;
    for(int i = 1; i <= n; i++){
        trie1.add_string(v[i - 1], i);
        trie2.add_string(v[i - 1], i);
    }

    while(m--){
        string p, q; cin >> p >> q;
        pair<int, int> range = trie1.get_range(p);
        if (range.first == -1) cout << "0\n";
        else cout << trie2.query(q, range) << "\n";
    }
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 25 / 25
• 서브태스크 3: 25 / 25
• 서브태스크 4: 40 / 40