oj.uz

Submission #1044768

# Submission time Handle Problem Language Result Execution time Memory
1044768 2024-08-05T13:23:35 Z aufan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 522 ms 671164 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 0ll;
                        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 253 ms 591828 KB Output is correct
2 Correct 210 ms 591824 KB Output is correct
3 Correct 229 ms 591700 KB Output is correct
4 Correct 216 ms 591880 KB Output is correct
5 Correct 208 ms 591820 KB Output is correct
6 Correct 217 ms 591704 KB Output is correct
7 Correct 237 ms 591904 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 669596 KB Output is correct
2 Correct 466 ms 667476 KB Output is correct
3 Correct 280 ms 626288 KB Output is correct
4 Correct 269 ms 625496 KB Output is correct
5 Correct 376 ms 640336 KB Output is correct
6 Correct 373 ms 640692 KB Output is correct
7 Correct 271 ms 629176 KB Output is correct
8 Correct 320 ms 649552 KB Output is correct
9 Correct 318 ms 646160 KB Output is correct
10 Correct 288 ms 635476 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 606444 KB Output is correct
2 Correct 260 ms 600840 KB Output is correct
3 Correct 265 ms 602544 KB Output is correct
4 Correct 252 ms 602124 KB Output is correct
5 Correct 250 ms 601780 KB Output is correct
6 Correct 260 ms 602544 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 591828 KB Output is correct
2 Correct 210 ms 591824 KB Output is correct
3 Correct 229 ms 591700 KB Output is correct
4 Correct 216 ms 591880 KB Output is correct
5 Correct 208 ms 591820 KB Output is correct
6 Correct 217 ms 591704 KB Output is correct
7 Correct 237 ms 591904 KB Output is correct
8 Correct 487 ms 669596 KB Output is correct
9 Correct 466 ms 667476 KB Output is correct
10 Correct 280 ms 626288 KB Output is correct
11 Correct 269 ms 625496 KB Output is correct
12 Correct 376 ms 640336 KB Output is correct
13 Correct 373 ms 640692 KB Output is correct
14 Correct 271 ms 629176 KB Output is correct
15 Correct 320 ms 649552 KB Output is correct
16 Correct 318 ms 646160 KB Output is correct
17 Correct 288 ms 635476 KB Output is correct
18 Correct 272 ms 606444 KB Output is correct
19 Correct 260 ms 600840 KB Output is correct
20 Correct 265 ms 602544 KB Output is correct
21 Correct 252 ms 602124 KB Output is correct
22 Correct 250 ms 601780 KB Output is correct
23 Correct 260 ms 602544 KB Output is correct
24 Correct 482 ms 664204 KB Output is correct
25 Correct 522 ms 671164 KB Output is correct
26 Correct 462 ms 661520 KB Output is correct
27 Correct 296 ms 629172 KB Output is correct
28 Correct 465 ms 658092 KB Output is correct
29 Correct 350 ms 628540 KB Output is correct