Submission #1218176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218176		bncodero_o123	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	248 ms	198316 KiB

selling_rna

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define name "code"
using namespace std;

const int max_n= 1e5;
string s[max_n + 2];

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

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

struct TRIE {
    struct NODE {
        NODE* child[4];
        int l, r, exist;
        NODE() {
            for(int i= 0; i < 4; ++i) child[i]= NULL;
            l= max_n, r= -1, exist= 0;
        }
    }* root;

    TRIE() : root(new NODE()) {}

    void add(string s) {
        NODE* cur= root;
        for(char c : s) {
            int id= get_val(c);
            if(cur -> child[id] == NULL) cur -> child[id]= new NODE();
            cur= cur -> child[id];
        }
        ++cur -> exist;
    }

    void add(string s, int p) {
        NODE* cur= root;
        for(char c : s) {
            int id= get_val(c);
            cur= cur -> child[id];
            cur -> l= min(cur -> l, p);
            cur -> r= max(cur -> r, p);
        }
    }

    int idx;
    string str;
    void sort(NODE* cur) {
        if(cur == root) idx= 0, str= "";
        for(int i= 0; i < cur -> exist; ++i) s[idx++]= str;
        for(int i= 0; i < 4; ++i)
            if(cur -> child[i] != NULL) {
                str.push_back(get_char(i));
                sort(cur -> child[i]);
                str.pop_back();
            }
    }

    pii get(string s) {
        NODE* cur= root;
        for(char c : s) {
            int id= get_val(c);
            if(cur -> child[id] == NULL) return make_pair(-1, -1);
            cur= cur -> child[id];
        }
        return make_pair(cur -> l, cur -> r);
    }
} trie;

struct REV_TRIE {
    struct NODE {
        NODE* child[4];
        vector<int> idx;
        NODE() {
            for(int i= 0; i < 4; ++i) child[i]= NULL;
        }
    }* root;

    REV_TRIE() : root(new NODE()) {}

    void add(string s, int p) {
        NODE* cur= root;
        reverse(s.begin(), s.end());
        for(int c : s) {
            int id= get_val(c);
            if(cur -> child[id] == NULL) cur -> child[id]= new NODE();
            cur= cur -> child[id];
            (cur -> idx).push_back(p);
        }
    }

    void build(NODE* cur) {
        if((cur -> idx).size()) sort((cur -> idx).begin(), (cur -> idx).end());
        for(int i= 0; i < 4; ++i) {
            if(cur -> child[i] != NULL) build(cur -> child[i]);
        }
    }

    int get(int l, int r, string s) {
        if(l == -1) return 0;
        NODE* cur= root;
        reverse(s.begin(), s.end());
        for(char c : s) {
            int id= get_val(c);
            if(cur -> child[id] == NULL) return 0;
            cur= cur -> child[id];
        }

        int g= lower_bound((cur -> idx).begin(), (cur -> idx).end(), l) - (cur -> idx).begin();
        int h= upper_bound((cur -> idx).begin(), (cur -> idx).end(), r) - (cur -> idx).begin();
        return h - g;
    }
} rev_trie;

void solve() {
    int n, q; cin >> n >> q;
    for(int i= 0; i < n; ++i) {
        string t; cin >> t;
        trie.add(t);
    }

    trie.sort(trie.root);
    for(int i= 0; i < n; ++i) trie.add(s[i], i);
    for(int i= 0; i < n; ++i) rev_trie.add(s[i], i);
    rev_trie.build(rev_trie.root);

    for(int i= 0; i < q; ++i) {
        string p, q; cin >> p >> q;
        auto [l, r]= trie.get(p);
        cout << rev_trie.get(l, r, q) << '\n';
    }
}

signed main() {
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    int T= 1;
    for(; T > 0; --T) solve();

    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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