oj.uz

Submission #708954

# Submission time Handle Problem Language Result Execution time Memory
708954 2023-03-12T21:53:50 Z Johann Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 269 ms 211028 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct segtree
{
    int size;
    vi arr;
    vb active;
    void init(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        arr.assign(2 * size, 0);
        active.assign(2 * size, false);
    }
    void doInc(int x, int amount)
    {
        if (x < size || active[x])
            arr[x] += amount;
    }
    void propagate(int x)
    {
        if (x < size)
        {
            doInc(2 * x, arr[x]);
            doInc(2 * x + 1, arr[x]);
            arr[x] = 0;
        }
    }
    void increment(int l, int r) { increment(l, r, 1, 0, size); }
    void increment(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
        {
            doInc(x, 1);
            return;
        }
        if (r <= lx || rx <= l)
            return;
        int m = (lx + rx) / 2;
        increment(l, r, 2 * x, lx, m);
        increment(l, r, 2 * x + 1, m, rx);
    }
    void setState(int x, bool state) { setState(x, state, 1, 0, size); }
    void setState(int i, bool state, int x, int lx, int rx)
    {
        propagate(x);
        if (rx - lx == 1)
        {
            active[x] = state;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m)
            setState(i, state, 2 * x, lx, m);
        else
            setState(i, state, 2 * x + 1, m, rx);
    }
    int query(int i) { return query(i, 1, 0, size); }
    int query(int i, int x, int lx, int rx)
    {
        propagate(x);
        if (rx - lx == 1)
            return arr[x];
        int m = (lx + rx) / 2;
        if (i < m)
            return query(i, 2 * x, lx, m);
        else
            return query(i, 2 * x + 1, m, rx);
    }
};

vvi S;        // Sortiment von der Company
vvi P, Q;     // Prefixes and suffixes
vi Qin, Qout; // in idx and out idx for the range sums
segtree seg;

struct node
{
    int idx = 0; // of this node
    node *children[4] = {nullptr, nullptr, nullptr, nullptr};
    vi fixe; // suffixe or prefixe
    vi S;    // together with suffixes there are sorting
};
struct trie
{
    node *root = new node();
    void insert(vi &word, int id, bool type) { insert(root, 0, word, id, type); }
    void insert(node *r, int idx, vi &word, int id, int type)
    { // id to append to the fixe (type 0) and S (type 1)
        if (idx == sz(word))
        {
            if (type == 0)
                r->fixe.push_back(id);
            else
                r->S.push_back(id);
            return;
        }
        int next = word[idx];
        if (r->children[next] == nullptr)
            r->children[next] = new node();

        insert(r->children[next], idx + 1, word, id, type);
    }
};

trie Tsuff, Tpref;

void dfsInit(node *r, int &idx)
{
    for (int q : r->fixe)
        Qin[q] = ++idx;
    r->idx = idx; // knowing the correct prefix idx

    for (int i = 0; i < 4; ++i)
        if (r->children[i] != nullptr)
            dfsInit(r->children[i], idx);

    for (int q : r->fixe)
        Qout[q] = ++idx;
}

void answer(node *r, vi &word)
{
    int idx = 0;
    int i = 0;
    while (r != nullptr)
    {
        idx = r->idx;
        if (i >= sz(word))
            break;
        r = r->children[word[i++]];
    }
    seg.increment(0, idx + 1);
}

void dfsAnswer(node *r)
{
    for (int qid : r->fixe)
    {
        seg.setState(Qin[qid], true);
        seg.setState(Qout[qid], true);
    }
    for (int sid : r->S)
    {
        answer(Tpref.root, S[sid]);
    }

    for (int i = 0; i < 4; ++i)
        if (r->children[i] != nullptr)
            dfsAnswer(r->children[i]);

    for (int qid : r->fixe)
    {
        seg.setState(Qin[qid], false);
        seg.setState(Qout[qid], false);
    }
}

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

    int N, M;
    cin >> N >> M;

    S.resize(N);
    string rna, kundeP, kundeQ;
    vi decode(128);
    decode['A'] = 0, decode['C'] = 1, decode['G'] = 2, decode['U'] = 3;

    for (int i = 0; i < N; ++i)
    {
        cin >> rna;
        for (char c : rna)
            S[i].push_back(decode[c]);
        reverse(all(S[i]));
        Tsuff.insert(S[i], i, 1);
        reverse(all(S[i]));
    }

    P.resize(M), Q.resize(M);
    for (int i = 0; i < M; ++i)
    {
        cin >> kundeP >> kundeQ;
        for (char c : kundeP)
            P[i].push_back(decode[c]);
        Tpref.insert(P[i], i, 0);

        for (char c : kundeQ)
            Q[i].push_back(decode[c]);
        reverse(all(Q[i]));
        Tsuff.insert(Q[i], i, 0);
    }

    int idx = 0;
    Qin.resize(M), Qout.resize(M);
    dfsInit(Tpref.root, idx);
    ++idx;

    seg.init(idx);

    dfsAnswer(Tsuff.root);

    for (int q = 0; q < M; ++q)
        cout << seg.query(Qin[q]) - seg.query(Qout[q]) << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 211028 KB Output is correct
2 Correct 206 ms 202380 KB Output is correct
3 Correct 65 ms 28184 KB Output is correct
4 Correct 51 ms 28492 KB Output is correct
5 Correct 195 ms 174744 KB Output is correct
6 Correct 185 ms 175528 KB Output is correct
7 Correct 87 ms 37744 KB Output is correct
8 Correct 192 ms 149256 KB Output is correct
9 Correct 184 ms 134640 KB Output is correct
10 Correct 100 ms 77132 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11344 KB Output is correct
2 Correct 45 ms 7636 KB Output is correct
3 Correct 75 ms 10004 KB Output is correct
4 Correct 49 ms 8084 KB Output is correct
5 Correct 47 ms 7312 KB Output is correct
6 Correct 63 ms 9852 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 219 ms 211028 KB Output is correct
9 Correct 206 ms 202380 KB Output is correct
10 Correct 65 ms 28184 KB Output is correct
11 Correct 51 ms 28492 KB Output is correct
12 Correct 195 ms 174744 KB Output is correct
13 Correct 185 ms 175528 KB Output is correct
14 Correct 87 ms 37744 KB Output is correct
15 Correct 192 ms 149256 KB Output is correct
16 Correct 184 ms 134640 KB Output is correct
17 Correct 100 ms 77132 KB Output is correct
18 Correct 64 ms 11344 KB Output is correct
19 Correct 45 ms 7636 KB Output is correct
20 Correct 75 ms 10004 KB Output is correct
21 Correct 49 ms 8084 KB Output is correct
22 Correct 47 ms 7312 KB Output is correct
23 Correct 63 ms 9852 KB Output is correct
24 Correct 211 ms 180396 KB Output is correct
25 Correct 249 ms 184588 KB Output is correct
26 Correct 196 ms 177112 KB Output is correct
27 Correct 81 ms 31052 KB Output is correct
28 Correct 269 ms 64676 KB Output is correct
29 Correct 195 ms 38816 KB Output is correct