Cerinta completa

DNA is a nucleic acid present in the bodies of living things. Each piece of DNA contains a number of genes, some of which are beneficial and increase the DNA’s total health. Each gene has a health value, and the total health of a DNA is the sum of the health values of all the beneficial genes that occur as a substring in the DNA. We represent genes and DNA as non-empty strings of lowercase English alphabetic letters, and the same gene may appear multiple times as a susbtring of a DNA.

Given the following:

  • An array of beneficial gene strings, . Note that these gene sequences are not guaranteed to be distinct.
  • An array of gene health values, , where each is the health value for gene .
  • A set of DNA strands where the definition of each strand has three components, , , and , where string is a DNA for which genes are healthy.

Find and print the respective total healths of the unhealthiest (minimum total health) and healthiest (maximum total health) strands of DNA as two space-separated values on a single line.

Input Format

The first line contains an integer, , denoting the total number of genes.
The second line contains space-separated strings describing the respective values of (i.e., the elements of ).
The third line contains space-separated integers describing the respective values of (i.e., the elements of ).
The fourth line contains an integer, , denoting the number of strands of DNA to process.
Each of the subsequent lines describes a DNA strand in the form start end d, denoting that the healthy genes for DNA strand are and their respective correlated health values are .

Constraints

  • the sum of the lengths of all genes and DNA strands
  • It is guaranteed that each consists of lowercase English alphabetic letters only (i.e., a to z).

Output Format

Print two space-separated integers describing the respective total health of the unhealthiest and the healthiest strands of DNA.

Sample Input 0

6
a b c aa d b
1 2 3 4 5 6
3
1 5 caaab
0 4 xyz
2 4 bcdybc

Sample Output 0

0 19

Explanation 0

In the diagrams below, the ranges of beneficial genes for a specific DNA on the left are highlighed in green and individual instances of beneficial genes on the right are bolded. The total healths of the strands are:

  1. image
    The total health of caaab is .
  2. image
    The total health of xyz is , because it contains no beneficial genes.
  3. image
    The total health of bcdybc is .

The unhealthiest DNA strand is xyz with a total health of , and the healthiest DNA strand is caaab with a total health of . Thus, we print 0 19 as our answer.

Limbajul de programare folosit: cpp20

Cod:

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

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick() : n(0) {}
    explicit Fenwick(int n_) { init(n_); }

    void init(int n_) {
        n = n_;
        bit.assign(n + 2, 0);
    }

    void add(int idx, long long val) {
        for (int i = idx; i <= n; i += i & -i) bit[i] += val;
    }

    void range_add(int l, int r, long long val) {
        add(l, val);
        if (r + 1 <= n) add(r + 1, -val);
    }

    long long sum(int idx) const {
        long long s = 0;
        for (int i = idx; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

struct Op {
    int k;
    int qi;
    int sign;

    bool operator<(const Op& other) const {
        return k < other.k;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<string> genes(n);
    for (int i = 0; i < n; ++i) cin >> genes[i];

    vector<int> health(n);
    for (int i = 0; i < n; ++i) cin >> health[i];

    vector<array<int, 26>> go;
    go.reserve(2000005);
    go.emplace_back();
    go[0].fill(0);

    vector<int> fail;
    fail.reserve(2000005);
    fail.push_back(0);

    vector<int> term(n);

    for (int i = 0; i < n; ++i) {
        int node = 0;
        for (char ch : genes[i]) {
            int c = ch - 'a';
            int nxt = go[node][c];
            if (nxt == 0) {
                nxt = (int)go.size();
                go[node][c] = nxt;
                go.emplace_back();
                go.back().fill(0);
                fail.push_back(0);
            }
            node = nxt;
        }
        term[i] = node;
    }

    int nodes = (int)go.size();

    deque<int> q;
    for (int c = 0; c < 26; ++c) {
        int v = go[0][c];
        if (v != 0) q.push_back(v);
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop_front();

        for (int c = 0; c < 26; ++c) {
            int u = go[v][c];
            if (u != 0) {
                fail[u] = go[fail[v]][c];
                q.push_back(u);
            } else {
                go[v][c] = go[fail[v]][c];
            }
        }
    }

    vector<int> firstChild(nodes, -1), nextSibling(nodes, -1);
    for (int v = 1; v < nodes; ++v) {
        int p = fail[v];
        nextSibling[v] = firstChild[p];
        firstChild[p] = v;
    }

    vector<int> tin(nodes), tout(nodes);
    int timer = 0;

    vector<pair<int, int>> st;
    st.reserve(nodes);
    tin[0] = ++timer;
    st.push_back({0, firstChild[0]});

    while (!st.empty()) {
        int v = st.back().first;
        int& child = st.back().second;

        if (child != -1) {
            int u = child;
            child = nextSibling[u];
            tin[u] = ++timer;
            st.push_back({u, firstChild[u]});
        } else {
            tout[v] = timer;
            st.pop_back();
        }
    }

    int s;
    cin >> s;

    vector<string> dna(s);
    vector<Op> ops;
    ops.reserve(2 * s);

    for (int qi = 0; qi < s; ++qi) {
        int l, r;
        string d;
        cin >> l >> r >> d;
        dna[qi] = move(d);

        ops.push_back({r, qi, +1});
        if (l > 0) ops.push_back({l - 1, qi, -1});
    }

    sort(ops.begin(), ops.end());

    Fenwick fw(nodes + 2);
    vector<long long> answer(s, 0);

    int gi = 0;
    for (const Op& op : ops) {
        while (gi <= op.k) {
            int terminal = term[gi];
            fw.range_add(tin[terminal], tout[terminal], health[gi]);
            ++gi;
        }

        long long total = 0;
        int state = 0;
        const string& d = dna[op.qi];

        for (unsigned char ch : d) {
            state = go[state][ch - 'a'];
            total += fw.sum(tin[state]);
        }

        answer[op.qi] += (long long)op.sign * total;
    }

    long long mn = answer[0], mx = answer[0];
    for (long long v : answer) {
        mn = min(mn, v);
        mx = max(mx, v);
    }

    cout << mn << ' ' << mx << "\n";
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464632584

Link challenge: https://www.hackerrank.com/challenges/determining-dna-health/problem

Determining DNA Health