Submission #846926

#	Time	Username	Problem	Language	Result	Execution time	Memory
846926		thanh913	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1538 ms	197628 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
using ll = long long;
using pii = pair<int, int>;
 
const int N = 1e5+5, M = 2e6+5, B = 150, m1 = 1e9+7, m2 = 1e9+9, p = 53;
 
int mul1(ll x, ll y) {return x*y % m1;}
int mul2(ll x, ll y) {return x*y % m2;}
 
int pw1[N], pw2[N];
struct hasher {
    int n;
    vector<int> h1, h2;
    void init(string &s) {
        n = s.size();
        h1.assign(n+2, 0); h2.assign(n+2, 0);
        for (int i = n; i >= 1; i--) {
            h1[i] = (h1[i+1] + mul1(s[i-1], pw1[100000-i])) % m1;
            h2[i] = (h2[i+1] + mul2(s[i-1], pw2[100000-i])) % m2;
        }
    }
    pii get(int l) {
        return {mul1(h1[l], pw1[l]), mul2(h2[l], pw2[l])};
    }
};
 
//--------------------------------------
int n, m, ans[N];
string a[N], x[N], y[N];
hasher ha[N], hy[N];
pii vy[N];
 
struct trie {
    struct miniTrie {
        int n, ed[M];
        int nxt[M][4];
        void clear() {
            while (n >= 0) {
                ed[n] = nxt[n][0] = nxt[n][1] = nxt[n][2] = nxt[n][3] = 0;
                n--;
            }
            n = 0;
        }
 
        void add(string &s) {
            int id = 0, lim = max(0, ((int)s.size())-B+1);
            for (int i = s.size() - 1; i >= lim; i--) {
                if (!nxt[id][s[i]]) {
                    nxt[id][s[i]] = ++n;
                }
                id = nxt[id][s[i]]; ed[id]++;
            }
        }
 
        int get(string &s) {
            int id = 0;
            for (int i = s.size() - 1; i >= 0; i--) {
                if (!nxt[id][s[i]]) return 0;
                id = nxt[id][s[i]];
            }
            return ed[id];
        }
    } tree;
 
    int n, nxt[M][4];
    vector<int> idx[M], qr[M], qr2[M];
 
    void add(string &s, int idx) {
        int id = 0;
        for (auto u : s) {
            int &val = nxt[id][u];
            if (!val) val = ++n;
            id = val;
        }
        qr[id].push_back(idx);
    }
 
    vector<pii> vals;
    void solve(int id, int len) {
        for (auto u : idx[id]) {
            tree.add(a[u]);
            if (a[u].size() >= B) { 
                for (auto v : qr2[id]) {
                    int pos = a[u].size() - y[v].size() + 1;
                    if (ha[u].get(pos) == vy[v]) {
                        ans[v]++;
                    }
                }
            }
        }
        
        for (auto u : qr[id]) {
            if (y[u].size() >= B) continue;
            ans[u] += tree.get(y[u]);
        }
        tree.clear();
 
        for (auto u : idx[id]) {
            if (a[u].size() < len+1) continue;
            int &id2 = nxt[id][a[u][len]];
            if (!id2) id2 = ++n;
            idx[id2].push_back(u);
        }
        idx[id].resize(0);
        for (int i = 0; i < 4; i++) {
            if (nxt[id][i]) solve(nxt[id][i], len+1);
        }
    }
} tree;
 
void conv(string &s) {
    for (auto &u : s) {
        if (u == 'A') u = 0;
        if (u == 'G') u = 1;
        if (u == 'C') u = 2;
        if (u == 'U') u = 3;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < N; i++) {
        pw1[i] = mul1(pw1[i-1], p);
        pw2[i] = mul2(pw2[i-1], p);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; conv(a[i]);
        ha[i].init(a[i]);
        tree.idx[0].push_back(i);
    }
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        conv(x[i]); conv(y[i]);
        hy[i].init(y[i]); vy[i] = hy[i].get(1);
        tree.add(x[i], i);
    }
    for (int i = 1; i <= tree.n; i++) {
        for (auto u : tree.qr[i]) {
            if (y[i].size() >= B)
                tree.qr2[i].push_back(u);
        }
    }
    tree.solve(0, 0);
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void trie::miniTrie::add(std::string&)':
selling_rna.cpp:52:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   52 |                 if (!nxt[id][s[i]]) {
      |                                  ^
selling_rna.cpp:53:33: warning: array subscript has type 'char' [-Wchar-subscripts]
   53 |                     nxt[id][s[i]] = ++n;
      |                                 ^
selling_rna.cpp:55:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   55 |                 id = nxt[id][s[i]]; ed[id]++;
      |                                  ^
selling_rna.cpp: In member function 'int trie::miniTrie::get(std::string&)':
selling_rna.cpp:62:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |                 if (!nxt[id][s[i]]) return 0;
      |                                  ^
selling_rna.cpp:63:34: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |                 id = nxt[id][s[i]];
      |                                  ^
selling_rna.cpp: In member function 'void trie::add(std::string&, int)':
selling_rna.cpp:75:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   75 |             int &val = nxt[id][u];
      |                                ^
selling_rna.cpp: In member function 'void trie::solve(int, int)':
selling_rna.cpp:103:29: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |             if (a[u].size() < len+1) continue;
      |                 ~~~~~~~~~~~~^~~~~~~
selling_rna.cpp:104:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |             int &id2 = nxt[id][a[u][len]];
      |                                         ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40