Submission #377438

#	Time	Username	Problem	Language	Result	Execution time	Memory
377438		dolphingarlic	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	509 ms	396144 KiB

selling_rna

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

struct TrieNode {
    TrieNode *c[4];
    int tin, tout;
    vector<int> terminal;
    vector<tuple<int, int, int>> queries;
    unordered_map<int, int> bit;

    TrieNode() { for (int i = 0; i < 4; i++) c[i] = nullptr; }
};

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

void insert(string &s, TrieNode *node, int i) {
    for (char c : s) {
        int idx = get_idx(c);
        if (!node->c[idx]) node->c[idx] = new TrieNode();
        node = node->c[idx];
    }
    node->terminal.push_back(i);
}

TrieNode *retrieve(string &s, TrieNode *node) {
    for (char c : s) {
        int idx = get_idx(c);
        if (!node->c[idx]) return nullptr;
        node = node->c[idx];
    }
    return node;
}

int n, m, label[100001];
vector<int> comp;

void euler_tour(TrieNode *node, int &timer) {
    node->tin = ++timer;
    if (node->terminal.size()) {
        for (int i : node->terminal) label[i] = timer;
        comp.push_back(timer);
    }
    for (int i = 0; i < 4; i++) if (node->c[i]) euler_tour(node->c[i], timer);
    node->tout = timer;
}

int ans[100001];

void merge(TrieNode *A, TrieNode *B) {
    if (A->bit.size() > B->bit.size()) swap(A->bit, B->bit);
    for (pair<int, int> i : A->bit) B->bit[i.first] += i.second;
}

int find_lb(int val) {
    return lower_bound(comp.begin(), comp.end(), val) - comp.begin() + 1;
}

int find_ub(int val) {
    return upper_bound(comp.begin(), comp.end(), val) - comp.begin();
}

void update(unordered_map<int, int> &bit, int pos, int val) {
    for (; pos <= comp.size(); pos += pos & -pos) bit[pos] += val;
}

int query(unordered_map<int, int> &bit, int l, int r) {
    int ans = 0;
    for (; r; r -= r & -r) ans += bit[r];
    for (l--; l; l -= l & -l) ans -= bit[l];
    return ans;
}

void traverse(TrieNode *node) {
    for (int i = 0; i < 4; i++) if (node->c[i]) {
        traverse(node->c[i]);
        merge(node->c[i], node);
    }
    for (int i : node->terminal) update(node->bit, find_lb(label[i]), 1);

    for (auto i : node->queries) {
        int idx, l, r;
        tie(idx, l, r) = i;
        ans[idx] = query(node->bit, find_lb(l), find_ub(r));
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    TrieNode *pref = new TrieNode(), *suff = new TrieNode();
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        insert(s, pref, i);
        reverse(s.begin(), s.end());
        insert(s, suff, i);
    }

    int timer = 0;
    euler_tour(pref, timer);

    for (int i = 1; i <= m; i++) {
        string s, t;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        TrieNode *s_node = retrieve(s, pref), *t_node = retrieve(t, suff);
        if (s_node && t_node)
            t_node->queries.push_back({i, s_node->tin, s_node->tout});
    }

    traverse(suff);
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'void update(std::unordered_map<int, int>&, int, int)':
selling_rna.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (; pos <= comp.size(); pos += pos & -pos) bit[pos] += val;
      |            ~~~~^~~~~~~~~~~~~~

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