Submission #1125817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125817		borisAngelov	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	552 ms	499444 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2000005;
const int SIGMA = 26;

int n, q;

string words[maxn];

struct TrieNode
{
    int children[SIGMA];

    TrieNode()
    {
        for (int i = 0; i < SIGMA; ++i)
        {
            children[i] = -1;
        }
    }
};

struct Trie
{
    int cntNodes = 1;
    TrieNode tree[maxn];
    int whichNode[maxn];

    void addString(const string& curr, int wordIdx)
    {
        int node = 1;

        for (int i = 0; i < curr.size(); ++i)
        {
            int idx = (curr[i] - 'A');

            if (tree[node].children[idx] == -1)
            {
                tree[node].children[idx] = ++cntNodes;
            }

            node = tree[node].children[idx];
        }

        whichNode[wordIdx] = node;
    }

    int tim = 1;
    int in[maxn];
    int out[maxn];

    void dfs(int node)
    {
        in[node] = tim++;

        for (int i = 0; i < SIGMA; ++i)
        {
            if (tree[node].children[i] != -1)
            {
                dfs(tree[node].children[i]);
            }
        }

        out[node] = tim - 1;
    }

    int findString(const string& curr)
    {
        int node = 1;

        for (int i = 0; i < curr.size(); ++i)
        {
            int idx = (curr[i] - 'A');

            if (tree[node].children[idx] == -1)
            {
                return -1;
            }

            node = tree[node].children[idx];
        }

        return node;
    }
};

Trie pref;
Trie suff;

// x y type idx +/-
vector<tuple<int, int, int, int, int>> queries;
int answers[maxn];

struct Fenwick
{
    int tree[maxn];
    int MAX;

    void init(int _MAX)
    {
        MAX = _MAX;
        fill(tree, tree + MAX + 1, 0);
    }

    void update(int pos, int add)
    {
        for (; pos <= MAX; pos += (pos & (-pos)))
        {
            tree[pos] += add;
        }
    }

    int query(int pos)
    {
        int result = 0;

        for (; pos >= 1; pos -= (pos & (-pos)))
        {
            result += tree[pos];
        }

        return result;
    }
};

Fenwick bit;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> q;

    for (int i = 1; i <= n; ++i)
    {
        cin >> words[i];
        pref.addString(words[i], i);
        reverse(words[i].begin(), words[i].end());
        suff.addString(words[i], i);
    }

    pref.dfs(1);
    suff.dfs(1);

    for (int i = 1; i <= n; ++i)
    {
        int x = pref.in[pref.whichNode[i]];
        int y = suff.in[suff.whichNode[i]];
        queries.push_back({x, y, 0, -1, -1});
    }

    bit.init(maxn - 1);

    for (int i = 1; i <= q; ++i)
    {
        string word1, word2;
        cin >> word1 >> word2;
        reverse(word2.begin(), word2.end());

        int prefNode = pref.findString(word1);
        int suffNode = suff.findString(word2);

        int inp = (prefNode == -1 ? -1 : pref.in[prefNode]);
        int outp = (prefNode == -1 ? -1 : pref.out[prefNode]);
        int ins = (suffNode == -1 ? -1 : suff.in[suffNode]);
        int outs = (suffNode == -1 ? -1 : suff.out[suffNode]);

        //cout << i << " :: " << inp << " " << outp << " " << ins << " " << outs << endl;

        queries.push_back({outp, outs, 1, i, +1});
        queries.push_back({inp - 1, outs, 1, i, -1});
        queries.push_back({outp, ins - 1, 1, i, -1});
        queries.push_back({inp - 1, ins - 1, 1, i, +1});
    }

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

    for (auto [x, y, type, idx, coeff] : queries)
    {
        if (type == 0)
        {
            if (y != -1) bit.update(y, +1);
        }
        else
        {
            if (x == -1 || y == -1) answers[idx] = 0;
            else answers[idx] += coeff * bit.query(y);
        }
    }

    for (int i = 1; i <= q; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

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