제출 #1288973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288973		nemkho	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	191 ms	220024 KiB

selling_rna

#include<bits/stdc++.h>
#define ll long long
#define pr pair <int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e6 + 5;
int n, m, pos[30];
string s[N];
struct Trie1
{
    int child[N][4], sta[N], en[N], cnt = 0;
    void make_trie ()
    {
        for (int i = 1; i < N; i++)
        {
            sta[i] = 1e9+5;
            en[i] = 0;
        }
    }
    void add (string &s, int idx)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int k = pos[s[i] - 'A'];
            if (child[u][k] == 0)
                child[u][k] = ++cnt;
            u = child[u][k];
            sta[u] = min(idx, sta[u]);
            en[u] = max(idx, en[u]);
        }
        sta[u] = min(idx, sta[u]);
        en[u] = max(idx, en[u]);
    }
    pr get (string &s)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int k = pos[s[i] - 'A'];
            if (child[u][k] != 0)
                u = child[u][k];
            else
                return {-1, -1};
        }
        return {sta[u], en[u]};
    }
} trie1;
struct Trie2
{
    int child[N][4], cnt = 0;
    vector <int> id[N];
    void add (string &s, int idx)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int k = pos[s[i] - 'A'];
            if (child[u][k] == 0)
                child[u][k] = ++cnt;
            u = child[u][k];
            id[u].push_back(idx);
        }
    }
    int get (string &s, int l, int r)
    {
        int u = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int k = pos[s[i] - 'A'];
            if (child[u][k] != 0)
                u = child[u][k];
            else
                return 0;
        }
        int L = lower_bound(id[u].begin(), id[u].end(), l) - id[u].begin();
        int R = upper_bound(id[u].begin(), id[u].end(), r) - id[u].begin() - 1;
        return (R - L + 1);
    }
} trie2;
void inp()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
}
void solve()
{
    pos[0] = 0;
    pos['G' - 'A'] = 1;
    pos['C' - 'A'] = 2;
    pos['U' - 'A'] = 3;
    trie1.make_trie();
    sort(s + 1, s + n + 1);
//    for (int i = 1; i <= n; i++)
//        cout << s[i] << "\n";
    for (int i = 1; i <= n; i++)
    {
        trie1.add(s[i], i);
        reverse(s[i].begin(), s[i].end());
        trie2.add(s[i], i);
    }
    for (int i = 1; i <= m; i++)
    {
        string s1, s2;
        cin >> s1 >> s2;
        reverse(s2.begin(), s2.end());
        pr pre = trie1.get(s1);
        if (pre.fi == -1)
            cout << 0;
        else
        {
            cout << trie2.get(s2, pre.fi, pre.se);
        }
        cout << "\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    inp();
    solve();
}

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