oj.uz

Submission #1104400

# Submission time Handle Problem Language Result Execution time Memory
1104400 2024-10-23T15:59:54 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 941 ms 575412 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct trie1 {
    vector<unordered_map<char, int>> a;
    vector<int> l, r;
    int n = 0;
    int oo = 1e9;
    unordered_map<char, int> temp;
    
    void start() {
        a.push_back(temp);
        l.push_back(oo);
        r.push_back(0);
    }
    
    void add(string s, int id) {
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (a[pos][s[i]] == 0) {
                a[pos][s[i]] = ++n;
                a.push_back(temp);
                l.push_back(id);
                r.push_back(id);
                pos = n;
            } else {
                pos = a[pos][s[i]];
            }
            r[pos] = id;
        }
    }
    
    pair<int, int> query(string s) {
        int pos = 0;
        for (auto i : s) {
            if (a[pos].find(i) == a[pos].end()) return {-1, -1};
            pos = a[pos][i];
        }
        return {l[pos], r[pos]};
    }
};

struct trie2 {
    vector<unordered_map<char, int>> a;
    vector<vector<int>> b;
    int n = 0;
    unordered_map<char, int> temp;
    
    void start() {
        a.push_back(temp);
        b.push_back({});
    }
    
    void add(string s, int id) {
        int pos = 0;
        for (int i = 0; i < s.length(); i++) {
            if (a[pos][s[i]] == 0) {
                a[pos][s[i]] = ++n;
                a.push_back(temp);
                b.push_back({});
                pos = n;
            } else {
                pos = a[pos][s[i]];
            }
            b[pos].push_back(id);
        }
    }
    
    int query(string s) {
        int pos = 0;
        for (auto i : s) {
            if (a[pos].find(i) == a[pos].end()) return -1;
            pos = a[pos][i];
        }
        return pos;
    }
};

const int MAX = 1e5 + 2;
int n, q;
string a[MAX];

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    trie1 chemwy;
    trie2 cheemwy;
    chemwy.start();
    cheemwy.start();
    for (int i = 1; i <= n; i++) {
        chemwy.add(a[i], i);
        reverse(a[i].begin(), a[i].end());
        cheemwy.add(a[i], i);
    }
    for (int i = 1; i <= cheemwy.n; i++) sort(cheemwy.b[i].begin(), cheemwy.b[i].end());
    for (int i = 1; i <= q; i++) {
        string s, t;
        cin >> s >> t;
        reverse(t.begin(), t.end());
        auto [l, r] = chemwy.query(s);
        if (l == -1) {
            cout << 0 << "\n";
            continue;
        }
        int temp = cheemwy.query(t);
        if (temp == -1) {
            cout << 0 << "\n";
            continue;
        }
        int x = upper_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), r) - cheemwy.b[temp].begin() - 1;
        int y = lower_bound(cheemwy.b[temp].begin(), cheemwy.b[temp].end(), l) - cheemwy.b[temp].begin();
        cout << x - y + 1 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

Compilation message

selling_rna.cpp: In member function 'void trie1::add(std::string, int)':
selling_rna.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp: In member function 'void trie2::add(std::string, int)':
selling_rna.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < s.length(); i++) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 3 ms 3664 KB Output is correct
4 Correct 2 ms 3588 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 2 ms 3408 KB Output is correct
7 Correct 3 ms 3576 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 502500 KB Output is correct
2 Correct 802 ms 475648 KB Output is correct
3 Correct 606 ms 416500 KB Output is correct
4 Correct 941 ms 397512 KB Output is correct
5 Correct 868 ms 567576 KB Output is correct
6 Correct 921 ms 575412 KB Output is correct
7 Correct 156 ms 19748 KB Output is correct
8 Correct 612 ms 343076 KB Output is correct
9 Correct 522 ms 296948 KB Output is correct
10 Correct 613 ms 285888 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4812 KB Output is correct
2 Correct 20 ms 5484 KB Output is correct
3 Correct 24 ms 5240 KB Output is correct
4 Correct 19 ms 4696 KB Output is correct
5 Correct 20 ms 5456 KB Output is correct
6 Correct 24 ms 5200 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 3 ms 3408 KB Output is correct
3 Correct 3 ms 3664 KB Output is correct
4 Correct 2 ms 3588 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 2 ms 3408 KB Output is correct
7 Correct 3 ms 3576 KB Output is correct
8 Correct 740 ms 502500 KB Output is correct
9 Correct 802 ms 475648 KB Output is correct
10 Correct 606 ms 416500 KB Output is correct
11 Correct 941 ms 397512 KB Output is correct
12 Correct 868 ms 567576 KB Output is correct
13 Correct 921 ms 575412 KB Output is correct
14 Correct 156 ms 19748 KB Output is correct
15 Correct 612 ms 343076 KB Output is correct
16 Correct 522 ms 296948 KB Output is correct
17 Correct 613 ms 285888 KB Output is correct
18 Correct 23 ms 4812 KB Output is correct
19 Correct 20 ms 5484 KB Output is correct
20 Correct 24 ms 5240 KB Output is correct
21 Correct 19 ms 4696 KB Output is correct
22 Correct 20 ms 5456 KB Output is correct
23 Correct 24 ms 5200 KB Output is correct
24 Correct 835 ms 411312 KB Output is correct
25 Correct 734 ms 411368 KB Output is correct
26 Correct 726 ms 406508 KB Output is correct
27 Correct 545 ms 342520 KB Output is correct
28 Correct 294 ms 72964 KB Output is correct
29 Correct 129 ms 11968 KB Output is correct