oj.uz

Submission #847045

# Submission time Handle Problem Language Result Execution time Memory
847045 2023-09-09T02:58:33 Z Tam_theguide Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 418 ms 485484 KB 
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, nxt[10*N][4], cnt, cnt2, l[N], r[N], minl[10*N], maxr[10*N], rnk[N], char_id[100];
vector<int> leaving[10*N][4], query_at[10*N];
string tmps[N], s[N], x[N], y[N];

void add(int id) {
    int u = 0;
    for (int j = s[id].size() - 1; j >= 0; j--) {
        char c = s[id][j];
        if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
        for (int i = 0; i < 4; i++) {
            if (i != char_id[c]) leaving[u][i].push_back(id);
        }
        u = nxt[u][char_id[c]];
    }

    for (int i = 0; i < 4; i++) leaving[u][i].push_back(id);
}

void add2(int id) {
    int u = 0;
    for (int j = y[id].size() - 1; j >= 0; j--) {
        char c = y[id][j];
        if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt2;
        u = nxt[u][char_id[c]];
    }

    query_at[u].push_back(id);
}


int BIT[N];
void update(int u, int v) {
    while (u <= n) {
        BIT[u] += v;
        u += (u & (-u));
    }
}

int get_pre(int u) {
    int ans = 0;
    while (u > 0) {
        ans += BIT[u];
        u -= (u & (-u));
    }
    return ans;
}

int get(int l, int r) {
    if (l > r) return 0;
    return get_pre(r) - get_pre(l-1);
}

int res[N];
void dfs(int u) {
    for (auto c: query_at[u])
    res[c] = get(l[c], r[c]);

    for (int i = 0; i < 4; i++) {
        if (!nxt[u][i]) continue;
        for (auto c: leaving[u][i])
        update(c, -1);
        dfs(nxt[u][i]);
        for (auto c: leaving[u][i])
        update(c, 1);
    }


}

stack<int> st;
void dfs_sort(int u) {
    /*
    for (auto c: query_at[u])
        rnk[c] = ++cnt2;
    for (int i = 0; i < 4; i++) {
        if (!nxt[u][i]) continue;
        dfs_sort(nxt[u][i]);
    }
    */
    st.push(u);
    while (!st.empty()) {
        int v = st.top();
        if (minl[v]) {
            st.pop();
            continue;
        }
        minl[v] = 1;
        for (auto c: query_at[v])
            rnk[c] = ++cnt2;
        for (int i = 3; i >= 0; i--) {
            if (!nxt[v][i]) continue;
            st.push(nxt[v][i]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("rna.inp", "r", stdin);
    //freopen("rna.out", "w", stdout);
    char_id['A'] = 0;
    char_id['U'] = 1;
    char_id['G'] = 2;
    char_id['C'] = 3;

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> tmps[i];
        reverse(tmps[i].begin(), tmps[i].end());
    }

    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (auto c: tmps[i]) {
            if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
            u = nxt[u][char_id[c]];
        }
        query_at[u].push_back(i);
    }

    dfs_sort(0);
    for (int i = 1; i <= cnt; i++) query_at[i].clear();
    cnt2 = cnt = 0;
    memset(nxt, 0, sizeof nxt);
    for (int i = 1; i <= n; i++) s[rnk[i]] = tmps[i];

    // for (int i = 1; i <= n; i++) add(i);
    for (int i = 1; i <= m; i++) {
        l[i] = n+1, r[i] = 0;
        cin >> x[i] >> y[i];
        add2(i);
    }

    for (int i = 1; i <= cnt2; i++)
        minl[i] = n+1, maxr[i] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (auto c: s[i]) {
            if (!nxt[u][char_id[c]]) break;
            u = nxt[u][char_id[c]];
            minl[u] = min(minl[u], i);
            maxr[u] = max(maxr[u], i);
        }
    }

    for (int i = 1; i <= cnt2; i++) {
        for (auto c: query_at[i]) {
            l[c] = minl[i];
            r[c] = maxr[i];
        }
        query_at[i].clear();
    }

    cnt = cnt2 = 0;
    memset(nxt, 0, sizeof nxt);
    for (int i = 1; i <= n; i++) add(i);
    for (int i = 1; i <= m; i++) {
        int u = 0;
        bool not_found = false;
        for (auto c: x[i]) {
            if (!nxt[u][char_id[c]]) {
                not_found = true;
                break;
            }

            u = nxt[u][char_id[c]];
        }

        if (!not_found) query_at[u].push_back(i);
    }


    for (int i = 1; i <= n; i++)
        update(i, 1);

    dfs(0);

    for (int i = 1; i <= m; i++) cout << res[i] << '\n';
    /*
    while (true) {
        int i, j;
        cin >> i >> j;
        for (auto c: leaving[i][j]) cout << c << ", ";
        cout << '\n';
    }
    */
}
/*
4 1
UAU
AA
AAUAAU
UAUUUA
AAUA A
*/
/*
1 1
AAUAAU
AAUA A
*/

Compilation message

selling_rna.cpp: In function 'void add(int)':
selling_rna.cpp:13:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
      |                             ^
selling_rna.cpp:13:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
      |                                                 ^
selling_rna.cpp:15:30: warning: array subscript has type 'char' [-Wchar-subscripts]
   15 |             if (i != char_id[c]) leaving[u][i].push_back(id);
      |                              ^
selling_rna.cpp:17:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |         u = nxt[u][char_id[c]];
      |                            ^
selling_rna.cpp: In function 'void add2(int)':
selling_rna.cpp:27:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt2;
      |                             ^
selling_rna.cpp:27:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   27 |         if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt2;
      |                                                 ^
selling_rna.cpp:28:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |         u = nxt[u][char_id[c]];
      |                            ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:121:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  121 |             if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
      |                                 ^
selling_rna.cpp:121:53: warning: array subscript has type 'char' [-Wchar-subscripts]
  121 |             if (!nxt[u][char_id[c]]) nxt[u][char_id[c]] = ++cnt;
      |                                                     ^
selling_rna.cpp:122:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  122 |             u = nxt[u][char_id[c]];
      |                                ^
selling_rna.cpp:145:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  145 |             if (!nxt[u][char_id[c]]) break;
      |                                 ^
selling_rna.cpp:146:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  146 |             u = nxt[u][char_id[c]];
      |                                ^
selling_rna.cpp:167:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  167 |             if (!nxt[u][char_id[c]]) {
      |                                 ^
selling_rna.cpp:172:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  172 |             u = nxt[u][char_id[c]];
      |                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 296272 KB Output is correct
2 Correct 62 ms 296288 KB Output is correct
3 Correct 62 ms 296272 KB Output is correct
4 Correct 62 ms 296484 KB Output is correct
5 Correct 62 ms 296272 KB Output is correct
6 Correct 61 ms 296384 KB Output is correct
7 Correct 62 ms 296272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 343124 KB Output is correct
2 Correct 248 ms 341072 KB Output is correct
3 Correct 386 ms 485484 KB Output is correct
4 Correct 399 ms 476240 KB Output is correct
5 Correct 328 ms 422480 KB Output is correct
6 Correct 335 ms 424528 KB Output is correct
7 Correct 154 ms 329232 KB Output is correct
8 Correct 329 ms 395692 KB Output is correct
9 Correct 334 ms 381520 KB Output is correct
10 Correct 247 ms 376740 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 299452 KB Output is correct
2 Correct 81 ms 299384 KB Output is correct
3 Correct 100 ms 299540 KB Output is correct
4 Correct 74 ms 298836 KB Output is correct
5 Correct 80 ms 299524 KB Output is correct
6 Correct 83 ms 299600 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 296272 KB Output is correct
2 Correct 62 ms 296288 KB Output is correct
3 Correct 62 ms 296272 KB Output is correct
4 Correct 62 ms 296484 KB Output is correct
5 Correct 62 ms 296272 KB Output is correct
6 Correct 61 ms 296384 KB Output is correct
7 Correct 62 ms 296272 KB Output is correct
8 Correct 202 ms 343124 KB Output is correct
9 Correct 248 ms 341072 KB Output is correct
10 Correct 386 ms 485484 KB Output is correct
11 Correct 399 ms 476240 KB Output is correct
12 Correct 328 ms 422480 KB Output is correct
13 Correct 335 ms 424528 KB Output is correct
14 Correct 154 ms 329232 KB Output is correct
15 Correct 329 ms 395692 KB Output is correct
16 Correct 334 ms 381520 KB Output is correct
17 Correct 247 ms 376740 KB Output is correct
18 Correct 77 ms 299452 KB Output is correct
19 Correct 81 ms 299384 KB Output is correct
20 Correct 100 ms 299540 KB Output is correct
21 Correct 74 ms 298836 KB Output is correct
22 Correct 80 ms 299524 KB Output is correct
23 Correct 83 ms 299600 KB Output is correct
24 Correct 288 ms 341072 KB Output is correct
25 Correct 317 ms 342100 KB Output is correct
26 Correct 283 ms 340816 KB Output is correct
27 Correct 418 ms 453200 KB Output is correct
28 Correct 288 ms 336408 KB Output is correct
29 Correct 144 ms 314544 KB Output is correct