oj.uz

Submission #1044773

# Submission time Handle Problem Language Result Execution time Memory
1044773 2024-08-05T13:24:49 Z aufan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 387 ms 422120 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 348320 KB Output is correct
2 Correct 156 ms 348224 KB Output is correct
3 Correct 156 ms 348244 KB Output is correct
4 Correct 163 ms 348244 KB Output is correct
5 Correct 149 ms 348240 KB Output is correct
6 Correct 146 ms 348244 KB Output is correct
7 Correct 148 ms 348240 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 422120 KB Output is correct
2 Correct 274 ms 419756 KB Output is correct
3 Correct 208 ms 368464 KB Output is correct
4 Correct 205 ms 368468 KB Output is correct
5 Correct 205 ms 393964 KB Output is correct
6 Correct 216 ms 394576 KB Output is correct
7 Correct 211 ms 372568 KB Output is correct
8 Correct 265 ms 393560 KB Output is correct
9 Correct 244 ms 389712 KB Output is correct
10 Correct 234 ms 381780 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 360360 KB Output is correct
2 Correct 220 ms 356276 KB Output is correct
3 Correct 216 ms 358536 KB Output is correct
4 Correct 211 ms 356952 KB Output is correct
5 Correct 204 ms 356812 KB Output is correct
6 Correct 213 ms 358060 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 348320 KB Output is correct
2 Correct 156 ms 348224 KB Output is correct
3 Correct 156 ms 348244 KB Output is correct
4 Correct 163 ms 348244 KB Output is correct
5 Correct 149 ms 348240 KB Output is correct
6 Correct 146 ms 348244 KB Output is correct
7 Correct 148 ms 348240 KB Output is correct
8 Correct 274 ms 422120 KB Output is correct
9 Correct 274 ms 419756 KB Output is correct
10 Correct 208 ms 368464 KB Output is correct
11 Correct 205 ms 368468 KB Output is correct
12 Correct 205 ms 393964 KB Output is correct
13 Correct 216 ms 394576 KB Output is correct
14 Correct 211 ms 372568 KB Output is correct
15 Correct 265 ms 393560 KB Output is correct
16 Correct 244 ms 389712 KB Output is correct
17 Correct 234 ms 381780 KB Output is correct
18 Correct 224 ms 360360 KB Output is correct
19 Correct 220 ms 356276 KB Output is correct
20 Correct 216 ms 358536 KB Output is correct
21 Correct 211 ms 356952 KB Output is correct
22 Correct 204 ms 356812 KB Output is correct
23 Correct 213 ms 358060 KB Output is correct
24 Correct 264 ms 415432 KB Output is correct
25 Correct 304 ms 421248 KB Output is correct
26 Correct 306 ms 412572 KB Output is correct
27 Correct 258 ms 371136 KB Output is correct
28 Correct 387 ms 398288 KB Output is correct
29 Correct 290 ms 377284 KB Output is correct