oj.uz

Submission #865870

# Submission time Handle Problem Language Result Execution time Memory
865870 2023-10-25T01:25:25 Z phongcd Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 160 ms 146288 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 146288 KB Output is correct
2 Correct 151 ms 139080 KB Output is correct
3 Correct 67 ms 64216 KB Output is correct
4 Correct 67 ms 62816 KB Output is correct
5 Correct 119 ms 143752 KB Output is correct
6 Correct 120 ms 144812 KB Output is correct
7 Correct 43 ms 15896 KB Output is correct
8 Correct 117 ms 92860 KB Output is correct
9 Correct 102 ms 78792 KB Output is correct
10 Correct 85 ms 82244 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3288 KB Output is correct
2 Correct 15 ms 2488 KB Output is correct
3 Correct 18 ms 2988 KB Output is correct
4 Correct 14 ms 2468 KB Output is correct
5 Correct 15 ms 2592 KB Output is correct
6 Correct 19 ms 2908 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 147 ms 146288 KB Output is correct
9 Correct 151 ms 139080 KB Output is correct
10 Correct 67 ms 64216 KB Output is correct
11 Correct 67 ms 62816 KB Output is correct
12 Correct 119 ms 143752 KB Output is correct
13 Correct 120 ms 144812 KB Output is correct
14 Correct 43 ms 15896 KB Output is correct
15 Correct 117 ms 92860 KB Output is correct
16 Correct 102 ms 78792 KB Output is correct
17 Correct 85 ms 82244 KB Output is correct
18 Correct 19 ms 3288 KB Output is correct
19 Correct 15 ms 2488 KB Output is correct
20 Correct 18 ms 2988 KB Output is correct
21 Correct 14 ms 2468 KB Output is correct
22 Correct 15 ms 2592 KB Output is correct
23 Correct 19 ms 2908 KB Output is correct
24 Correct 152 ms 121824 KB Output is correct
25 Correct 160 ms 122088 KB Output is correct
26 Correct 149 ms 121284 KB Output is correct
27 Correct 72 ms 61688 KB Output is correct
28 Correct 128 ms 35028 KB Output is correct
29 Correct 55 ms 12100 KB Output is correct