oj.uz

Submission #847039

# Submission time Handle Problem Language Result Execution time Memory
847039 2023-09-09T02:39:22 Z Tam_theguide Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 419 ms 485228 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 78 ms 296440 KB Output is correct
2 Correct 62 ms 296272 KB Output is correct
3 Correct 61 ms 296272 KB Output is correct
4 Correct 63 ms 296484 KB Output is correct
5 Correct 63 ms 296272 KB Output is correct
6 Correct 62 ms 296272 KB Output is correct
7 Correct 63 ms 296272 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 343204 KB Output is correct
2 Correct 253 ms 341056 KB Output is correct
3 Correct 389 ms 485228 KB Output is correct
4 Correct 393 ms 476448 KB Output is correct
5 Correct 313 ms 422604 KB Output is correct
6 Correct 318 ms 424276 KB Output is correct
7 Correct 134 ms 329044 KB Output is correct
8 Correct 332 ms 395692 KB Output is correct
9 Correct 317 ms 381544 KB Output is correct
10 Correct 246 ms 376656 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 299452 KB Output is correct
2 Correct 82 ms 299344 KB Output is correct
3 Correct 83 ms 299592 KB Output is correct
4 Correct 74 ms 298880 KB Output is correct
5 Correct 80 ms 299520 KB Output is correct
6 Correct 84 ms 299428 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 296440 KB Output is correct
2 Correct 62 ms 296272 KB Output is correct
3 Correct 61 ms 296272 KB Output is correct
4 Correct 63 ms 296484 KB Output is correct
5 Correct 63 ms 296272 KB Output is correct
6 Correct 62 ms 296272 KB Output is correct
7 Correct 63 ms 296272 KB Output is correct
8 Correct 206 ms 343204 KB Output is correct
9 Correct 253 ms 341056 KB Output is correct
10 Correct 389 ms 485228 KB Output is correct
11 Correct 393 ms 476448 KB Output is correct
12 Correct 313 ms 422604 KB Output is correct
13 Correct 318 ms 424276 KB Output is correct
14 Correct 134 ms 329044 KB Output is correct
15 Correct 332 ms 395692 KB Output is correct
16 Correct 317 ms 381544 KB Output is correct
17 Correct 246 ms 376656 KB Output is correct
18 Correct 79 ms 299452 KB Output is correct
19 Correct 82 ms 299344 KB Output is correct
20 Correct 83 ms 299592 KB Output is correct
21 Correct 74 ms 298880 KB Output is correct
22 Correct 80 ms 299520 KB Output is correct
23 Correct 84 ms 299428 KB Output is correct
24 Correct 292 ms 341072 KB Output is correct
25 Correct 303 ms 342252 KB Output is correct
26 Correct 286 ms 340988 KB Output is correct
27 Correct 419 ms 453200 KB Output is correct
28 Correct 294 ms 336400 KB Output is correct
29 Correct 125 ms 314388 KB Output is correct