Submission #1191276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191276		DangKhoizzzz	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	208 ms	220164 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e9;
const int maxn = 2e6 + 7;

// ‘A’, ‘G’, ‘C’, ‘U’
//  A    B    C    D

struct node
{
    int child[4];
    node() {for(int i = 0; i < 4; i++) child[i] = -1;}
};

void modify(string &s)
{
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == 'G') s[i] = 'B';
        else if(s[i] == 'U') s[i] = 'D';
    }
}

vector <node> revtrie;
vector <node> nortrie;
vector <int> pos[maxn];

pii range[maxn];
string s[maxn];
int n , m;

void add_nor(string &s , int id)
{
    int cur = 0;
    for(char ch: s)
    {
        int c = ch - 'A';
        if(nortrie[cur].child[c] == -1)
        {
            nortrie[cur].child[c] = nortrie.size();
            nortrie.push_back(node());
        }
        cur = nortrie[cur].child[c];
        range[cur].fi = min(range[cur].fi , id);
        range[cur].se = max(range[cur].se , id);
    }
}

void add_rev(string &s , int id)
{
    int cur = 0;
    for(char ch: s)
    {
        int c = ch - 'A';
        if(revtrie[cur].child[c] == -1)
        {
            revtrie[cur].child[c] = revtrie.size();
            revtrie.push_back(node());
        }
        cur = revtrie[cur].child[c];
        pos[cur].push_back(id);
    }
}

pii get_range(string &pre)
{
    int cur = 0;
    for(char ch: pre)
    {
        int c = ch - 'A';
        if(nortrie[cur].child[c] == -1) return {-1 , -1};
        cur = nortrie[cur].child[c];
    }
    return range[cur];
}

int counting(string &pre , string &suf)
{
    int cur = 0;
    pii rr = get_range(pre);
    if(rr.fi == -1) return 0;

    for(char ch: suf)
    {
        int c = ch - 'A';
        if(revtrie[cur].child[c] == -1)
        {
            return 0;
        }
        cur = revtrie[cur].child[c];
    }

    return (int)(upper_bound(pos[cur].begin() , pos[cur].end() , rr.se) - pos[cur].begin())
    - (int)(lower_bound(pos[cur].begin() , pos[cur].end() , rr.fi) - pos[cur].begin());
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i]; modify(s[i]);
    }
    nortrie.push_back(node());
    revtrie.push_back(node());
    sort(s+1 , s+n+1);
    range[0] = (pii){1 , n};
    for(int i = 1; i < maxn; i++) range[i] = (pii){n+1 , 0};
    for(int i = 1; i <= n; i++)
    {
        add_nor(s[i] , i);
        reverse(s[i].begin() , s[i].end());
        add_rev(s[i] , i);
    }
    for(int i = 0; i < maxn; i++)
    {
        sort(pos[i].begin() , pos[i].end());
    }

    for(int i = 1; i <= m; i++)
    {
        string pre , suf; cin >> pre >> suf;
        reverse(suf.begin() , suf.end());
        modify(pre); modify(suf);
        cout << counting(pre , suf) << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //freopen("inp.txt" , "r" , stdin);
    //freopen("out.txt" , "w" , stdout);
    solve();
    return 0;
}

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