Submission #1190208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190208		Dinh_Van_Tung	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	502 ms	221976 KiB

selling_rna

/*
     ()_()    ()_()
    ( o.o )  ( -.- )
     > ^ <    (")(")
*/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
#define ff(i, a, b, j) for (int i = (a), bb = (b), jj = (j); i <= bb; i += jj)
#define rf(i, a, b, j) for (int i = (a), bb = (b), jj = (j); i >= bb; i -= jj)
#define lshift(x, i) ((x) << (i))
#define rshift(x, i) ((x) >> (i))
#define checkbit(x, i) (((x) >> (i)) & 1ll)
#define cnt_bit1(x) __builtin_popcountll((x))
#define clz(x) __builtin_clzll((x)) // count leading zeros
#define ctz(x) __builtin_ctzll((x)) // count trailing zeros
#define ll long long
#define ull unsigned long long
#define ld long double
#define db double
#define pi acos(-1)
#define maxn 100005
#define mod 1000000007

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

char fake(int k) {
    if (k == 0) {
        return 'A';
    }
    else if (k == 1) {
        return 'C';
    }
    else if (k == 2) {
        return 'G';
    }
    return 'U';
}

string arr_string[maxn];

struct prefixTrie {
    struct Node {
        Node* child[4];
        int l, r, isEnd;
        Node() {
            memset(child, NULL, sizeof child);
            l = 1e9;
            r = -1e9;
            isEnd = 0;
        }
    };

    Node* root;
    int timeDFS;

    prefixTrie() {
        root = new Node();
        timeDFS = 0;
    }

    void Add(string s) {
        Node* cur = root;
        for (auto c : s) {
            int k = real(c);
            if (cur->child[k] == NULL) {
                cur->child[k] = new Node();
            }
            cur = cur->child[k];
        }
        cur->isEnd += 1;
        return;
    }

    pii Find(string s) {
        Node* cur = root;
        for (auto c : s) {
            int k = real(c);
            if (cur->child[k] == NULL) {
                return {1e9, -1e9};
            }
            cur = cur->child[k];
        }
        return {cur->l, cur->r};
    }

    void DFS(Node* cur, string s) {
        if (cur->isEnd) {
            cur->l = cur->r = ++timeDFS;
            arr_string[timeDFS] = s;
            ff (i, 2, cur->isEnd, 1) {
                cur->r = ++timeDFS;
                arr_string[timeDFS] = s;
            }
        }
        ff (k, 0, 3, 1) {
            if (cur->child[k] != NULL) {
                DFS(cur->child[k], s + fake(k));
                cur->l = min(cur->l, cur->child[k]->l);
                cur->r = max(cur->r, cur->child[k]->r);
            }
        }
        return;
    }
};

struct suffixTrie {
    struct Node {
        Node* child[4];
        vector<int> Vector;
        bool check_sort;
        Node() {
            memset(child, NULL, sizeof child);
            check_sort = false;
        }
    };

    Node* root;
    suffixTrie() {
        root = new Node();
    }

    void Add(string s, int id) {
        reverse(s.begin(), s.end());
        Node* cur = root;
        cur->Vector.push_back(id);
        for (auto c : s) {
            int k = real(c);
            if (cur->child[k] == NULL) {
                cur->child[k] = new Node();
            }
            cur = cur->child[k];
            cur->Vector.push_back(id);
        }
        return;
    }

    int Find(string s, int l, int r) {
        reverse(s.begin(), s.end());
        Node* cur = root;
        for (auto c : s) {
            int k = real(c);
            if (cur->child[k] == NULL) {
                return 0;
            }
            cur = cur->child[k];
        }

        if (cur->check_sort) {
            cur->check_sort = true;
            sort(cur->Vector.begin(), cur->Vector.end());
        }
        int L = lower_bound(cur->Vector.begin(), cur->Vector.end(), l) - cur->Vector.begin();
        int R = upper_bound(cur->Vector.begin(), cur->Vector.end(), r) - cur->Vector.begin();
        return R - L;
    }
};

int n, m;
prefixTrie pTrie;
suffixTrie sTrie;

void input() {
    cin >> n >> m;
    ff (i, 1, n, 1) {
        string s;
        cin >> s;
        pTrie.Add(s);
    }
    return;
}

void solve() {
    pTrie.DFS(pTrie.root, "");
    ff (i, 1, n, 1) {
        sTrie.Add(arr_string[i], i);
    }

    while (m--) {
        string prefix, suffix;
        cin >> prefix >> suffix;
        pii p = pTrie.Find(prefix);
        if (p.fi == 1e9 && p.se == -1e9) {
            cout << 0 << '\n';
            continue;
        }
        cout << sTrie.Find(suffix, p.fi, p.se) << '\n';
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int test_case = 1;
//    cin >> test_case;
    ff (i, 1, test_case, 1) {
        input();
        solve();
    }
    return 0;
}
/*
     ()_()    ()_()
    ( o.o )  ( -.- )
     > ^ <    (")(")
*/

Compilation message (stderr)

selling_rna.cpp: In constructor 'prefixTrie::Node::Node()':
selling_rna.cpp:63:27: warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]
   63 |             memset(child, NULL, sizeof child);
      |                           ^~~~
In file included from /usr/include/features.h:486,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from selling_rna.cpp:6:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:57:1: note:   declared here
   57 | __NTH (memset (void *__dest, int __ch, size_t __len))
      | ^~~~~
selling_rna.cpp: In constructor 'suffixTrie::Node::Node()':
selling_rna.cpp:129:27: warning: passing NULL to non-pointer argument 2 of 'void* memset(void*, int, size_t)' [-Wconversion-null]
  129 |             memset(child, NULL, sizeof child);
      |                           ^~~~
In file included from /usr/include/features.h:486,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/c++config.h:586,
                 from /usr/include/c++/11/cassert:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:33,
                 from selling_rna.cpp:6:
/usr/include/x86_64-linux-gnu/bits/string_fortified.h:57:1: note:   declared here
   57 | __NTH (memset (void *__dest, int __ch, size_t __len))
      | ^~~~~

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