Submission #865870

#	Time	Username	Problem	Language	Result	Execution time	Memory
865870		phongcd	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	160 ms	146288 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 2e5 + 2;
const int M = 19;
const ll MOD = 1e9 + 7;
const ll INF = 2e9;
const ll base = 311;
const ll base2 = 1e4 + 7;
const int BLOCK_SIZE = 400;
 
int n, m;
int cur = -1, cur2 = -1;
int cid[200];
 
void maximize(int &a, int b) {
    if (a < b) a = b;
}
 
void minimize(int &a, int b) {
    if (a > b) a = b;
}
 
struct Trie {
    struct node {
        int l, r, child[4];
    }; vector <node> a;
 
    int new_node() {
        node tmp;
        memset(tmp.child, -1, sizeof tmp.child);
        tmp.l = INF, tmp.r = -INF;
        a.push_back(tmp);
        return ++cur;
    }
    
    void add_node(string s, int id) {
        int pos = 0, n = s.size();
        for (int i = 0; i < n; i ++) {
            int j = cid[s[i]];
            if (a[pos].child[j] < 0) {
                int tmp = new_node();
                a[pos].child[j] = tmp;
            }
            pos = a[pos].child[j];
            minimize(a[pos].l, id);
            maximize(a[pos].r, id);
        }
    }
 
    ii getrange(string s) {
        int pos = 0, n = s.size();
        for (int i = 0; i < n; i ++) {
            int j = cid[s[i]];
            if (a[pos].child[j] < 0) return {-1, -1};
            pos = a[pos].child[j];
        }
        return {a[pos].l, a[pos].r};
    }
} trie;
 
struct ReTrie {
    struct node {
        int child[4];
        vector <int> idx;
    }; vector <node> a;
 
    int new_node() {
        node tmp;
        memset(tmp.child, -1, sizeof tmp.child);
        a.push_back(tmp);
        return ++cur2;
    }
 
    void add_node(string s, int id) {
        reverse(all(s));
        int pos = 0, n = s.size();
        for (int i = 0; i < n; i ++) {
            int j = cid[s[i]];
            if (a[pos].child[j] < 0) {
                int tmp = new_node();
                a[pos].child[j] = tmp;
            }
            pos = a[pos].child[j];
            a[pos].idx.push_back(id);
        }
    }
 
    int getans(string s, int l, int r) {
        reverse(all(s));
        int pos = 0, n = s.size();
        for (int i = 0; i < n; i ++) {
            int j = cid[s[i]];
            if (a[pos].child[j] < 0) return 0;
            pos = a[pos].child[j];
        }
        
        int i = lower_bound(all(a[pos].idx), l) - a[pos].idx.begin();
        int j = upper_bound(all(a[pos].idx), r) - a[pos].idx.begin();
        return j - i;
    }
} trie2;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
  
    cid['A'] = 0, cid['G'] = 1, cid['C'] = 2, cid['U'] = 3;
 
    cin >> n >> m;
    vector <string> a(n);
    for (int i = 0; i < n; i ++) cin >> a[i];
 
    sort(all(a));
 
    trie.new_node();
    trie2.new_node();
    for (int i = 0; i < n; i ++) {
        trie.add_node(a[i], i);
        trie2.add_node(a[i], i);
    }
 
    while (m --) {
        string p, s;
        cin >> p >> s;
        ii range = trie.getrange(p);
        cout << trie2.getans(s, range.fi, range.se) << '\n';
    }
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add_node(std::string, int)':
selling_rna.cpp:49:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   49 |             int j = cid[s[i]];
      |                             ^
selling_rna.cpp: In member function 'std::pair<int, int> Trie::getrange(std::string)':
selling_rna.cpp:63:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |             int j = cid[s[i]];
      |                             ^
selling_rna.cpp: In member function 'void ReTrie::add_node(std::string, int)':
selling_rna.cpp:88:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |             int j = cid[s[i]];
      |                             ^
selling_rna.cpp: In member function 'int ReTrie::getans(std::string, int, int)':
selling_rna.cpp:102:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |             int j = cid[s[i]];
      |                             ^

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