oj.uz

Submission #1044792

# Submission time Handle Problem Language Result Execution time Memory
1044792 2024-08-05T13:34:23 Z aufan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 320 ms 340604 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<int> cnt(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'];
                        cnt[nw] += 1;
                }
        };

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

                return cnt[nw];
        };

        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() == '$') {
                        ans[j] -= query(q);
                } else if (p.back() == 'a') {
                        ans[j] += query(q);
                }
        }

        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:58:13: warning: unused variable 'ptr' [-Wunused-variable]
   58 |         int ptr = 0;
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 304716 KB Output is correct
2 Correct 132 ms 304724 KB Output is correct
3 Correct 140 ms 304724 KB Output is correct
4 Correct 126 ms 304720 KB Output is correct
5 Correct 132 ms 304704 KB Output is correct
6 Correct 124 ms 304728 KB Output is correct
7 Correct 146 ms 304720 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 317084 KB Output is correct
2 Correct 187 ms 317780 KB Output is correct
3 Correct 241 ms 313736 KB Output is correct
4 Correct 192 ms 313940 KB Output is correct
5 Correct 223 ms 312404 KB Output is correct
6 Correct 156 ms 312460 KB Output is correct
7 Correct 201 ms 320792 KB Output is correct
8 Correct 226 ms 321864 KB Output is correct
9 Correct 186 ms 321880 KB Output is correct
10 Correct 174 ms 314452 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 316532 KB Output is correct
2 Correct 166 ms 311476 KB Output is correct
3 Correct 173 ms 313524 KB Output is correct
4 Correct 167 ms 312748 KB Output is correct
5 Correct 163 ms 311732 KB Output is correct
6 Correct 171 ms 313776 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 304716 KB Output is correct
2 Correct 132 ms 304724 KB Output is correct
3 Correct 140 ms 304724 KB Output is correct
4 Correct 126 ms 304720 KB Output is correct
5 Correct 132 ms 304704 KB Output is correct
6 Correct 124 ms 304728 KB Output is correct
7 Correct 146 ms 304720 KB Output is correct
8 Correct 178 ms 317084 KB Output is correct
9 Correct 187 ms 317780 KB Output is correct
10 Correct 241 ms 313736 KB Output is correct
11 Correct 192 ms 313940 KB Output is correct
12 Correct 223 ms 312404 KB Output is correct
13 Correct 156 ms 312460 KB Output is correct
14 Correct 201 ms 320792 KB Output is correct
15 Correct 226 ms 321864 KB Output is correct
16 Correct 186 ms 321880 KB Output is correct
17 Correct 174 ms 314452 KB Output is correct
18 Correct 204 ms 316532 KB Output is correct
19 Correct 166 ms 311476 KB Output is correct
20 Correct 173 ms 313524 KB Output is correct
21 Correct 167 ms 312748 KB Output is correct
22 Correct 163 ms 311732 KB Output is correct
23 Correct 171 ms 313776 KB Output is correct
24 Correct 179 ms 321180 KB Output is correct
25 Correct 220 ms 325800 KB Output is correct
26 Correct 193 ms 319260 KB Output is correct
27 Correct 201 ms 316868 KB Output is correct
28 Correct 320 ms 340604 KB Output is correct
29 Correct 264 ms 327280 KB Output is correct