Submission #1236427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236427		goldenbull	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	245 ms	291720 KiB

selling_rna

#include <bits/stdc++.h>

///----------------[shorthand macros]---------------------------------------
#define fi              first
#define se              second

#define pb              push_back
#define all(x)          x.begin(), x.end()
#define cast(a, b)      static_cast<a>(b)

#define MASK(n)        ((n >= 64 ? ~0ULL : ((1ULL << (n)) - 1ULL)))
#define BIT(n, i)      (((n) >> (i)) & 1)
#define SET(n, i)      (n = ((n) | (1 << (i))))
#define UNSET(n, i)    (n = ((n) & ~(1 << (i))))
#define FLIP(n, i)     (n = ((n) ^ (1 << (i))))

#define el '\n'

using namespace std;

///-------------[type aliases]------------------------------------
template <typename T>
using ve    = vector<T>;
using ll    = long long;
using ull   = unsigned ll;
using db    = double;
using vi    = ve<int>;
using vll   = ve<ll>;
using vdb   = ve<db>;
using vb    = ve<bool>;
using ii    = pair<int, int>;
using pll   = pair<ll, ll>;

///--------------------[constants]------------------------------------------
const ll MAX = 1e6 + 7;
const ll MOD = 1e9 + 7;
const ll inf = 2e9 + 7;

const int MAX_NODE = 2e6 + 7;

int mp[256];
char d[4] = {'A', 'C', 'G', 'U'};

///---------------------[structs]-------------------------------------------
struct Trie
{
    struct Node
    {
        Node* child[4];
        int ext, l, r;
        Node() : ext(0), l(inf), r(-inf)
        {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
        }
    };

    Node* root;

    Trie()
    {
        root = new Node();
    }

    void add(const string& s, int id)
    {
        Node* p = root;
        for (auto i : s)
        {
            int c = mp[i];
            if (!p->child[c])
            {
                p->child[c] = new Node();
            }
            p = p->child[c];

            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
        p->ext++;
    }

    void str_sort(Node* p, string& str, ve<string>& res)
    {
        for (int i = 0; i < p->ext; i++)
            res.pb(str);

        for (int i = 0; i < 4; i++)
        {
            if (!p->child[i]) continue;
            str += d[i];
            str_sort(p->child[i], str, res);
            str.pop_back();
        }
    }

    ii get_range(const string& s)
    {
        Node* p = root;
        for (auto i : s)
        {
            int c = mp[i];
            if (!p->child[c]) return ii(-1, -1);
            p = p->child[c];
        }
        return ii(p->l, p->r);
    }
};

struct RevTrie
{
    struct Node
    {
        Node* child[4];
        vi id;
        int ext;
        Node() : ext(0)
        {
            for (int i = 0; i < 4; i++) child[i] = nullptr;
        }
    };

    Node* root;

    RevTrie()
    {
        root = new Node();
    }

    void add(const string& s, int id)
    {
        Node* p = root;
        for (int i = s.size()-1; i >= 0; i--)
        {
            int c = mp[s[i]];
            if (!p->child[c])
            {
                p->child[c] = new Node();
            }
            p = p->child[c];
            p->id.pb(id);
        }
        p->ext++;
    }

    int query(string& s, ii range)
    {
        reverse(all(s));
        Node* p = root;
        for (auto i : s)
        {
            int c = mp[i];
            if (!p->child[c]) return 0;
            p = p->child[c];
        }

        auto l = lower_bound(all(p->id), range.fi);
        auto r = upper_bound(all(p->id), range.se);

        return r - l;
    }
};

///---------------------[globals]-------------------------------------------
int n, m;
ve<string> vs;

Trie T;
RevTrie rT;

///-----------------[helper functions]--------------------------------------
void sort_strings(ve<string>& vs)
{
    Trie voi;
    while (!vs.empty())
    {
        voi.add(vs.back(), 0);
        vs.pop_back();
    }
    string tmp;
    voi.str_sort(voi.root, tmp, vs);
}

///------------------[main execution]---------------------------------------
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
    // freopen(".inp", "r", stdin);
    // freopen(".out", "w", stdout);

    mp['A'] = 0;
    mp['C'] = 1;
    mp['G'] = 2;
    mp['U'] = 3;

    cin >> n >> m;
    vs.resize(n);
    for (auto& i : vs) cin >> i;

    sort_strings(vs);
    for (int i = 0; i < n; i++)
    {
        T.add(vs[i], i);
        rT.add(vs[i], i);
    }

    while (m--)
    {
        string s1, s2;
        cin >> s1 >> s2;
        ii r = T.get_range(s1);
        int res = rT.query(s2, r);
        cout << res << el;
    }

    return 0;
}

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