Submission #1279932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279932		han^	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	182 ms	218688 KiB

selling_rna

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define N 1000005
using namespace std;

int n, q;
string s[N];

int stranform(char x)
{
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    return 3;
}

struct Trie
{
    struct Node
    {
        Node* c[4];
        int l, r;
        Node()
        {
            For (i, 0, 3) c[i] = 0;
            l = 2e9;
            r = 0;
        }
    };
    Node* root;
    Trie()
    {
        root = new Node();
    }
    void add (string s, int id)
    {
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                p->c[x] = new Node();
            p = p->c[x];
            if (id < p->l) p->l = id;
            if (id > p->r) p->r = id;
        }
    }
    ii get (string s)
    {
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform(s[i]);
            if (!p->c[x])
                return {2e9, 2e9};
            p = p->c[x];
        }
        return {p->l, p->r};
    }
};

struct RTrie
{
    struct Node
    {
        Node* c[4];
        vector<int> id;
        Node()
        {
            For (i, 0, 3) c[i] = 0;
        }
    };
    Node* root;
    RTrie()
    {
        root = new Node();
    }
    void add (string s, int id)
    {
        reverse (s.begin(), s.end() );
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                p->c[x] = new Node();
            p = p->c[x];
            p->id.push_back (id);
        }
    }
    int get (string s, ii k)
    {
        int l = k.fi, r = k.se;
        if (l == r && l == 2e9)
            return 0;
        Node* p = root;
        For (i, 0, (int) s.size() - 1)
        {
            int x = stranform (s[i]);
            if (!p->c[x])
                return 0;
            p = p->c[x];
        }
        return upper_bound (p->id.begin(), p->id.end(), r) - lower_bound (p->id.begin(), p->id.end(), l);
    }
};

int main()
{
    ios_base::sync_with_stdio (0);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> n >> q;
    For (i, 1, n) cin >> s[i];
    sort (s + 1, s + 1 + n);

    Trie t1;
    RTrie t2;
    For (i, 1, n)
    {
        t1.add (s[i], i);
        t2.add (s[i], i);
    }

    while (q--)
    {
        string p, q;
        cin >> p >> q;
        reverse (q.begin(), q.end() );
        cout << t2.get (q, t1.get (p) ) << "\n";
    }
    return 0;
}

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