Submission #1267622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267622		yoshi_33550336	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	267 ms	330764 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
void init()
{
}
namespace Trie1
{
struct Node
{
    int32_t child[26]{};
    int l = 100000;
    int r = -1;
};
Node nodes[2000001];
int cur = 1;
inline int try_push_back(int x, int c, int idx)
{
    if (!nodes[x].child[c])
        nodes[x].child[c] = cur++;
    int y = nodes[x].child[c];
    nodes[y].l = min(nodes[y].l, idx);
    nodes[y].r = max(nodes[y].r, idx);
    return y;
}
void insertString(string &s, int idx)
{
    int cur = 0;
    for (auto &i : s)
        cur = try_push_back(cur, i - 'A', idx);
}
pair<int, int> getRange(string &s)
{
    int cur = 0;
    for (auto &i : s)
    {
        cur = nodes[cur].child[i - 'A'];
        if (!cur)
            return {100000, -1};
    }
    return {nodes[cur].l, nodes[cur].r};
}
}; // namespace Trie1
namespace Trie2
{
struct Node
{
    int32_t child[26]{};
};
Node nodes[2000001];
vector<pair<int, int>> s_cnt[2000001];
int cur = 1;
inline int try_push_back(int x, int c, int idx)
{
    if (!nodes[x].child[c])
        nodes[x].child[c] = cur++;
    int y = nodes[x].child[c];
    s_cnt[y].push_back({idx, (s_cnt[y].size() ? s_cnt[y].back().second : 0) + 1});
    return y;
}
void insertString(string &s, int idx)
{
    int cur = 0;
    for (auto &i : s)
        cur = try_push_back(cur, i - 'A', idx);
}
int getnStrings(string &s, int idx1, int idx2)
{
    if (idx1 > idx2)
        return 0;
    int cur = 0;
    for (auto &i : s)
    {
        cur = nodes[cur].child[i - 'A'];
        if (!cur)
            return 0;
    }
    int xc = upper_bound(s_cnt[cur].begin(), s_cnt[cur].end(), pair<int, int>{idx2, 100000}) - 1 - s_cnt[cur].begin();
    int yc = lower_bound(s_cnt[cur].begin(), s_cnt[cur].end(), pair<int, int>{idx1, 0}) - 1 - s_cnt[cur].begin();
    if (xc < 0)
        return 0;
    if (yc < 0)
        return s_cnt[cur][xc].second;
    return s_cnt[cur][xc].second - s_cnt[cur][yc].second;
}
}; // namespace Trie2

void Yoshi()
{
    int n, q;
    cin >> n >> q;
    vector<string> sp(n);
    for (auto &i : sp)
        cin >> i;
    sort(sp.begin(), sp.end());
    for (int i = 0; i < n; i++)
        Trie1::insertString(sp[i], i);
    for (int i = 0; i < n; i++)
        reverse(sp[i].begin(), sp[i].end()), Trie2::insertString(sp[i], i);
    for (int i = 0; i < q; i++)
    {
        string s, t;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        auto [a, b] = Trie1::getRange(s);
        cout << Trie2::getnStrings(t, a, b) << endl;
    }
}
signed main()
{
#ifndef yoshi_likes_e4
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(problem ".inp", "r"))
    {
        freopen(problem ".inp", "r", stdin);
        freopen(problem ".out", "w", stdout);
    }
#endif
    init();
    int t = 1;
#if multitest
    cin >> t;
#endif
    while (t--)
        Yoshi();
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(problem ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(problem ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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