oj.uz

Submission #865480

# Submission time Handle Problem Language Result Execution time Memory
865480 2023-10-24T09:03:37 Z phongcd Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 158 ms 144388 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);
        tmp.idx.clear();
        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:89:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   89 |             int j = cid[s[i]];
      |                             ^
selling_rna.cpp: In member function 'int ReTrie::getans(std::string, int, int)':
selling_rna.cpp:103:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  103 |             int j = cid[s[i]];
      |                             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 142488 KB Output is correct
2 Correct 152 ms 138676 KB Output is correct
3 Correct 68 ms 63992 KB Output is correct
4 Correct 70 ms 62756 KB Output is correct
5 Correct 116 ms 144388 KB Output is correct
6 Correct 125 ms 143532 KB Output is correct
7 Correct 40 ms 15952 KB Output is correct
8 Correct 115 ms 92096 KB Output is correct
9 Correct 101 ms 79052 KB Output is correct
10 Correct 86 ms 83268 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2776 KB Output is correct
2 Correct 22 ms 2268 KB Output is correct
3 Correct 27 ms 2396 KB Output is correct
4 Correct 14 ms 2136 KB Output is correct
5 Correct 22 ms 2136 KB Output is correct
6 Correct 25 ms 2520 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 147 ms 142488 KB Output is correct
9 Correct 152 ms 138676 KB Output is correct
10 Correct 68 ms 63992 KB Output is correct
11 Correct 70 ms 62756 KB Output is correct
12 Correct 116 ms 144388 KB Output is correct
13 Correct 125 ms 143532 KB Output is correct
14 Correct 40 ms 15952 KB Output is correct
15 Correct 115 ms 92096 KB Output is correct
16 Correct 101 ms 79052 KB Output is correct
17 Correct 86 ms 83268 KB Output is correct
18 Correct 19 ms 2776 KB Output is correct
19 Correct 22 ms 2268 KB Output is correct
20 Correct 27 ms 2396 KB Output is correct
21 Correct 14 ms 2136 KB Output is correct
22 Correct 22 ms 2136 KB Output is correct
23 Correct 25 ms 2520 KB Output is correct
24 Correct 151 ms 121396 KB Output is correct
25 Correct 158 ms 121920 KB Output is correct
26 Correct 151 ms 120776 KB Output is correct
27 Correct 78 ms 61684 KB Output is correct
28 Correct 132 ms 35224 KB Output is correct
29 Correct 57 ms 12012 KB Output is correct