oj.uz

Submission #847038

# Submission time Handle Problem Language Result Execution time Memory
847038 2023-09-09T02:37:13 Z Tam_theguide Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 418 ms 538196 KB 
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, nxt[10*N][5], cnt, cnt2, l[N], r[N], minl[10*N], maxr[10*N], rnk[N], char_id[100];
vector<int> leaving[10*N][5], 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 89 ms 349472 KB Output is correct
2 Correct 72 ms 349276 KB Output is correct
3 Correct 73 ms 349476 KB Output is correct
4 Correct 72 ms 349436 KB Output is correct
5 Correct 72 ms 349316 KB Output is correct
6 Correct 73 ms 349260 KB Output is correct
7 Correct 73 ms 349472 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 398020 KB Output is correct
2 Correct 262 ms 396128 KB Output is correct
3 Correct 381 ms 538196 KB Output is correct
4 Correct 382 ms 529232 KB Output is correct
5 Correct 320 ms 475444 KB Output is correct
6 Correct 328 ms 477264 KB Output is correct
7 Correct 148 ms 382032 KB Output is correct
8 Correct 343 ms 448872 KB Output is correct
9 Correct 326 ms 434516 KB Output is correct
10 Correct 261 ms 429652 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 353048 KB Output is correct
2 Correct 96 ms 352616 KB Output is correct
3 Correct 97 ms 352840 KB Output is correct
4 Correct 87 ms 352324 KB Output is correct
5 Correct 91 ms 352592 KB Output is correct
6 Correct 95 ms 352844 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 349472 KB Output is correct
2 Correct 72 ms 349276 KB Output is correct
3 Correct 73 ms 349476 KB Output is correct
4 Correct 72 ms 349436 KB Output is correct
5 Correct 72 ms 349316 KB Output is correct
6 Correct 73 ms 349260 KB Output is correct
7 Correct 73 ms 349472 KB Output is correct
8 Correct 220 ms 398020 KB Output is correct
9 Correct 262 ms 396128 KB Output is correct
10 Correct 381 ms 538196 KB Output is correct
11 Correct 382 ms 529232 KB Output is correct
12 Correct 320 ms 475444 KB Output is correct
13 Correct 328 ms 477264 KB Output is correct
14 Correct 148 ms 382032 KB Output is correct
15 Correct 343 ms 448872 KB Output is correct
16 Correct 326 ms 434516 KB Output is correct
17 Correct 261 ms 429652 KB Output is correct
18 Correct 89 ms 353048 KB Output is correct
19 Correct 96 ms 352616 KB Output is correct
20 Correct 97 ms 352840 KB Output is correct
21 Correct 87 ms 352324 KB Output is correct
22 Correct 91 ms 352592 KB Output is correct
23 Correct 95 ms 352844 KB Output is correct
24 Correct 310 ms 394444 KB Output is correct
25 Correct 310 ms 395184 KB Output is correct
26 Correct 298 ms 393964 KB Output is correct
27 Correct 418 ms 506192 KB Output is correct
28 Correct 297 ms 390152 KB Output is correct
29 Correct 136 ms 368300 KB Output is correct