제출 #1041110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041110		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	127 ms	146256 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];

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

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

int find_string(string x, string y)
{
    int cur = 0;
    for (char i : x)
    {
        if (!trie[0][cur][get_char(i)]) return(0);
        cur = trie[0][cur][get_char(i)];
    }
    int L = l[cur], R = r[cur];
    cur = 0;
    reverse(y.begin(), y.end());
    for (char i : y)
    {
        if (!trie[1][cur][get_char(i)]) return(0);
        cur = trie[1][cur][get_char(i)];
    }
    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: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40