Submission #1041058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041058		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	127 ms	150332 KiB

selling_rna

#include <bits/stdc++.h>
#define ii pair <int, int>
#define ll long long
#define llll pair <ll, ll>
#define ld long double
#define ull unsigned long long
#define el "\n"
#define sp " "
#define fi first
#define se second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define __lcm(a, b) (a / __gcd(a, b) * b)
#define sq(x) (x) * (x)
#define sqr(x) sqrtl(x)
#define cbr(x) cbrtl(x)
#define sz(a) (ll)(a.size())
using namespace std;

const ld PI = acos(-1); const ll INFL = 2e18 + 7; const int INFI = 1e9 + 7;

int n, q, trie[2][2000005][4], node[2], l[2000005], r[2000005];
string x, y, s[100005];
vector <int> pos[2000005];

void add_string(string s, int id)
{
    for (int j = 0; j <= 1; j++)
    {
        int cur = 0;
        for (char i : s)
        {
            int temp;
            if (i == 'A') temp = 0;
            else if (i == 'C') temp = 1;
            else if (i == 'G') temp = 2;
            else temp = 3;
            if (!trie[j][cur][temp]) trie[j][cur][temp] = ++node[j];
            cur = trie[j][cur][temp];
            if (j == 0)
            {
                if (!l[cur]) l[cur] = id;
                r[cur] = id;
            }
            else pos[cur].pub(id);
        }
        reverse(s.begin(), s.end());
    }
}

int find_string(string x, string y)
{
    int cur = 0;
    for (char i : x)
    {
        int temp;
        if (i == 'A') temp = 0;
        else if (i == 'C') temp = 1;
        else if (i == 'G') temp = 2;
        else temp = 3;
        if (!trie[0][cur][temp]) return(0);
        cur = trie[0][cur][temp];
    }
    int L = l[cur], R = r[cur];
    cur = 0;
    for (char i : y)
    {
        int temp;
        if (i == 'A') temp = 0;
        else if (i == 'C') temp = 1;
        else if (i == 'G') temp = 2;
        else temp = 3;
        if (!trie[1][cur][temp]) return(0);
        cur = trie[1][cur][temp];
    }
    return(upper_bound(pos[cur].begin(), pos[cur].end(), R) - lower_bound(pos[cur].begin(), pos[cur].end(), L));
}

void Solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) add_string(s[i], i);
    while (q--)
    {
        cin >> x >> y;
        cout << find_string(x, y) << el;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);  cin.tie(NULL);  cout.tie(0);
    
    Solve();
    return 0;
}

//coded by icyalmond

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