Submission #1104401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104401		Mahog	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	1111 ms	573056 KiB

selling_rna

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40