oj.uz

Submission #1044769

# Submission time Handle Problem Language Result Execution time Memory
1044769 2024-08-05T13:23:58 Z aufan Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 510 ms 668056 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 321 ms 591980 KB Output is correct
2 Correct 232 ms 591700 KB Output is correct
3 Correct 248 ms 591696 KB Output is correct
4 Correct 249 ms 591696 KB Output is correct
5 Correct 243 ms 591696 KB Output is correct
6 Correct 265 ms 591956 KB Output is correct
7 Correct 253 ms 591804 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 668056 KB Output is correct
2 Correct 510 ms 665688 KB Output is correct
3 Correct 327 ms 624480 KB Output is correct
4 Correct 309 ms 623956 KB Output is correct
5 Correct 412 ms 639320 KB Output is correct
6 Correct 403 ms 639832 KB Output is correct
7 Correct 352 ms 626888 KB Output is correct
8 Correct 381 ms 646900 KB Output is correct
9 Correct 370 ms 640080 KB Output is correct
10 Correct 310 ms 632152 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 605772 KB Output is correct
2 Correct 286 ms 600760 KB Output is correct
3 Correct 292 ms 602304 KB Output is correct
4 Correct 269 ms 601272 KB Output is correct
5 Correct 274 ms 601012 KB Output is correct
6 Correct 271 ms 602288 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 591980 KB Output is correct
2 Correct 232 ms 591700 KB Output is correct
3 Correct 248 ms 591696 KB Output is correct
4 Correct 249 ms 591696 KB Output is correct
5 Correct 243 ms 591696 KB Output is correct
6 Correct 265 ms 591956 KB Output is correct
7 Correct 253 ms 591804 KB Output is correct
8 Correct 495 ms 668056 KB Output is correct
9 Correct 510 ms 665688 KB Output is correct
10 Correct 327 ms 624480 KB Output is correct
11 Correct 309 ms 623956 KB Output is correct
12 Correct 412 ms 639320 KB Output is correct
13 Correct 403 ms 639832 KB Output is correct
14 Correct 352 ms 626888 KB Output is correct
15 Correct 381 ms 646900 KB Output is correct
16 Correct 370 ms 640080 KB Output is correct
17 Correct 310 ms 632152 KB Output is correct
18 Correct 311 ms 605772 KB Output is correct
19 Correct 286 ms 600760 KB Output is correct
20 Correct 292 ms 602304 KB Output is correct
21 Correct 269 ms 601272 KB Output is correct
22 Correct 274 ms 601012 KB Output is correct
23 Correct 271 ms 602288 KB Output is correct
24 Correct 476 ms 660104 KB Output is correct
25 Correct 506 ms 666560 KB Output is correct
26 Correct 464 ms 657768 KB Output is correct
27 Correct 298 ms 624324 KB Output is correct
28 Correct 457 ms 653488 KB Output is correct
29 Correct 365 ms 625052 KB Output is correct