Submission #1069815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069815		cpismylifeOwO	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	166 ms	185300 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e5 + 5;
const int BlockSize = 317;
const int MaxTrie = 2e6 + 5;

struct Que
{
    int l, r, id;

    Que() = default;

    Que(int _l, int _r, int _id)
    {
        l = _l;
        r = _r;
        id = _id;
    }
};

int n, m;
string arr[MaxN];
string pre[MaxN];
string suf[MaxN];

void Inp()
{
    cin >> n >> m;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
    for (int x = 1; x <= m; x++)
    {
        cin >> pre[x] >> suf[x];
    }
    sort(arr + 1, arr + n + 1);
}

struct Node
{
    int child[4];
    int exist, cnt, l, r;
    vector<int> contain;

    Node()
    {
        child[0] =  child[1] = child[2] = child[3] = -1;
        exist = cnt = 0;
        l = n + 1;
        r = 0;
        contain.clear();
    }
};

int curPos;
Node Trie[MaxTrie];
int res[MaxN];

int Cov(char a)
{
    if (a == 'C')
    {
        return 0;
    }
    if (a == 'U')
    {
        return 1;
    }
    if (a == 'G')
    {
        return 2;
    }
    return 3;
}

void Add(string s, int p)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            curPos++;
            Trie[curPos] = Node();
            Trie[pos].child[c] = curPos;
            Trie[pos].contain.push_back(p);
            Trie[pos].l = min(Trie[pos].l, p);
            Trie[pos].r = max(Trie[pos].r, p);
        }
        pos = Trie[pos].child[c];
        Trie[pos].l = min(Trie[pos].l, p);
        Trie[pos].r = max(Trie[pos].r, p);
        Trie[pos].cnt++;
    }
    Trie[pos].exist++;
}

pair<int, int> GetPlace(string s)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            return make_pair(-1, -1);
        }
        pos = Trie[pos].child[c];
    }
    return make_pair(Trie[pos].l, Trie[pos].r);
}

int BSearch(int pos, int k)
{
    int l = 0, r = (int)Trie[pos].contain.size() - 1, mid, res = -1;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (Trie[pos].contain[mid] <= k)
        {
            res = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return res + 1;
}

int Count(string s, int l, int r)
{
    int pos = 0;
    for (char x : s)
    {
        int c = Cov(x);
        if (Trie[pos].child[c] == -1)
        {
            return 0;
        }
        pos = Trie[pos].child[c];
    }
    return BSearch(pos, r) - BSearch(pos, l - 1);
}

vector<Que> query;

void Exc()
{
    curPos = 0;
    Trie[0] = Node();
    Trie[0].l = 1;
    Trie[0].r = n;
    for (int x = 1; x <= n; x++)
    {
        Add(arr[x], x);
    }
    for (int x = 1; x <= m; x++)
    {
        pair<int, int> p = GetPlace(pre[x]);
        if (p.first != -1)
        {
            query.push_back(Que(p.first, p.second, x));
        }
        else
        {
            res[x] = 0;
        }
        //cout << pre[x] << " " << p.first << " " << p.second << "\n";
    }
    curPos = 0;
    Trie[0] = Node();
    for (int x = 1; x <= n; x++)
    {
        reverse(arr[x].begin(), arr[x].end());
        Add(arr[x], x);
    }
    for (Que& x : query)
    {
        reverse(suf[x.id].begin(), suf[x.id].end());
        res[x.id] = Count(suf[x.id], x.l, x.r);
    }
    for (int x = 1; x <= m; x++)
    {
        cout << res[x] << "\n";
    }
}

int main()
{
    //freopen("D.INP", "r", stdin);
    //freopen("D.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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