Submission #708954

#	Time	Username	Problem	Language	Result	Execution time	Memory
708954		Johann	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	269 ms	211028 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40