제출 #1179899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1179899		ttn	Selling RNA Strands (JOI16_selling_rna)	C++20	35 / 100	177 ms	103496 KiB

selling_rna

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

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

int getChar(int n) {
    if (n == 1) return 'A';
    if (n == 2) return 'G';
    if (n == 3) return 'C';
    return 'U';
}

const int inf = 1e9;
struct Trie {
    struct Node {
        int l = inf;
        int r = -inf;
        int child[4];
        Node () {
            memset(child, 0, sizeof child);
        }
    };
    int cur = 0;
    Node node[1000005];

    void Add(const string &s, int id) {
        int u = 0;
        for (char c : s) {
            c = getNum(c);
            if (node[u].child[c] == 0) node[u].child[c] = ++cur;
            u = node[u].child[c];
            node[u].l = min(node[u].l, id);
            node[u].r = max(node[u].r, id);
        }
    }

    pair<int, int> Range(const string &s) {
        int u = 0;
        for (char c : s) {
            c = getNum(c);
            if (node[u].child[c] == 0) node[u].child[c] = ++cur;
            u = node[u].child[c];
        }
        return {node[u].l, node[u].r};
    }
};

struct RverTrie {
    struct Node {
        vector<int> ids;
        int child[4];
        Node () {
            memset(child, 0, sizeof child);
        }
    };
    int cur = 0;
    Node node[1000005];

    void Add(const string &s, int id) {
        int u = 0;
        for (char c : s) {
            c = getNum(c);
            if (node[u].child[c] == 0) node[u].child[c] = ++cur;
            u = node[u].child[c];
            node[u].ids.push_back(id);
        }
    }

    vector<int> getId(string &s) {
        reverse(s.begin(), s.end());
        int u = 0;
        vector<int> tmp;
        for (char c : s) {
            c = getNum(c);
            if (node[u].child[c] == 0) return tmp;
            u = node[u].child[c];
        }
        return node[u].ids;
    }
};


string a[200005];
int main () {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);

    Trie tri1;
    RverTrie tri2;
    for (int i = 0; i < n; i++) {
        tri1.Add(a[i], i);
        reverse(a[i].begin(), a[i].end());
        tri2.Add(a[i], i);
    }

    while (m--) {
        string p, q; cin >> p >> q;
        auto rag = tri1.Range(p);

        vector<int> v = tri2.getId(q);
        if (v.size() == 0 || rag.first == inf || rag.second == -inf) cout << 0 << '\n';
        else {
            int l = lower_bound(v.begin(), v.end(), rag.first) - v.begin();
            int r = upper_bound(v.begin(), v.end(), rag.second) - v.begin();
            cout << r-l << '\n';
        }
    }
    
    return 0;
}

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