Submission #1044773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044773		aufan	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	387 ms	422120 KiB

selling_rna

#include <bits/stdc++.h>
// #define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m;
        cin >> n >> m;

        vector<tuple<string, string, int>> v;
        for (int i = 0; i < n; i++) {
                string s;
                cin >> s;

                v.push_back({s + "]", "?", -1});
        }

        for (int i = 0; i < m; i++) {
                string p, q;
                cin >> p >> q;
                reverse(q.begin(), q.end());

                v.push_back({p + "$", q, i});
                v.push_back({p + "a", q, i});
        }
        sort(v.begin(), v.end());

        int id = 0;
        vector<vector<int>> ids(2222222);
        vector<vector<int>> ch(2222222, vector<int>(26));

        auto upd = [&](string s, int i) {
                int nw = 0;
                reverse(s.begin(), s.end());
                for (auto c : s) {
                        if (ch[nw][c - 'A'] == 0) ch[nw][c - 'A'] = ++id;
                        nw = ch[nw][c - 'A'];
                        ids[nw].push_back(i);
                }
        };

        auto query = [&](string s, int x) {
                int nw = 0;
                for (auto c : s) {
                        if (ch[nw][c - 'A'] == 0) return 0;
                        nw = ch[nw][c - 'A'];
                }

                int res = (int)ids[nw].size() - (upper_bound(ids[nw].begin(), ids[nw].end(), x) - ids[nw].begin());
                return res;
        };

        vector<int> l(m);
        for (int i = 0; i < (int)v.size(); i++) {
                auto &[p, q, j] = v[i];

                if (p.back() == '$') {
                        l[j] = i;
                }
        }

        int ptr = 0;
        vector<int> ans(m);
        for (int i = 0; i < (int)v.size(); i++) {
                auto &[p, q, j] = v[i];

                if (q == "?") {
                        p.pop_back();
                        upd(p, i);
                } else if (p.back() == 'a') {
                        ans[j] = query(q, l[j]);
                }
        }

        for (int i = 0; i < m; i++) cout << ans[i] << '\n';
        
        return 0;
}

Compilation message (stderr)

selling_rna.cpp: In function 'int32_t main()':
selling_rna.cpp:68:13: warning: unused variable 'ptr' [-Wunused-variable]
   68 |         int ptr = 0;
      |             ^~~

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