oj.uz

Submission #823714

# Submission time Handle Problem Language Result Execution time Memory
823714 2023-08-13T02:33:06 Z hafo Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 696 ms 289424 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e6 + 7;
const ll oo = 1e18 + 69;

int n, m, timer = 0, stq[maxn], enq[maxn], res[maxn], d[maxn];
string st1, st2;
vector<int> st[maxn];

struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x <= 2e6; x += x&-x) bit[x] += val;
    }

    int get(int x) {
        int ans = 0;
        for(; x; x -= x&-x) ans += bit[x];
        return ans;
    }

    int query(int l, int r) {
        return get(r) - get(l - 1);
    }

} bit;

int convert(char ch) {
    if(ch == 'A') return 0;
    if(ch == 'G') return 1;
    if(ch == 'C') return 2;
    return 3;
}

struct trie {
    struct node {
        node* child[4];
        vector<int> s;  

        node() {
            for(int i = 0; i < 4; i++) child[i] = NULL;
        }
    };

    node* root;

    trie() {
        root = new node();
    }

    void add(string &st, int id) {
        auto p = root;
        for(int i = 0; i < Size(st); i++) {
            int nxt = convert(st[i]);
            if(p -> child[nxt] == NULL) p -> child[nxt] = new node();
            p = p -> child[nxt];
            if(id > 0) p -> s.pb(id);
        }
        if(id < 0) p -> s.pb(id);
    }

    void dfs(node* u, int len) {
        ++timer;
        for(auto i:u -> s) {
            if(i > 0) st[i][len] = timer;
            else stq[-i] = timer;
        }

        for(int i = 0; i < 4; i++) {
            if(u -> child[i] == NULL) continue;
            dfs(u -> child[i], len + 1);
        }

        for(auto i:u -> s) 
            if(i < 0) enq[-i] = timer;
    }


    void dfs2(node* u, int len) {
        for(auto i:u -> s) {
            if(i > 0) bit.update(st[i][len], 1);
        }
        for(auto i:u -> s) {
            if(i < 0) res[-i] += bit.query(stq[-i], enq[-i]);
        }
        for(auto i:u -> s) {
            if(i > 0) bit.update(st[i][len], -1);
        }

        for(int i = 0; i < 4; i++) {
            if(u -> child[i] == NULL) continue;
            dfs2(u -> child[i], len + 1);
        }
    }

    void solve() {
        dfs2(root, 0);
     }

} pre, suf;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
        cin>>st1;
        st[i].resize(Size(st1) + 1);
        pre.add(st1, i);
        reverse(all(st1));
        suf.add(st1, i);
    }

    for(int i = 1; i <= m; i++) {
        cin>>st1>>st2;
        pre.add(st1, -i);
        reverse(all(st2));
        suf.add(st2, -i);
        d[i] = (Size(st1) == Size(st2)) + 1;
    }

    suf.dfs(suf.root, 0);
    pre.solve();
    timer = 0;
    pre.dfs(pre.root, 0);
    suf.solve();
    for(int i = 1; i <= m; i++) cout<<res[i] / d[i]<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47392 KB Output is correct
2 Correct 23 ms 47380 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 24 ms 47384 KB Output is correct
5 Correct 26 ms 47336 KB Output is correct
6 Correct 24 ms 47388 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 259592 KB Output is correct
2 Correct 696 ms 248424 KB Output is correct
3 Correct 643 ms 256420 KB Output is correct
4 Correct 638 ms 246680 KB Output is correct
5 Correct 439 ms 285924 KB Output is correct
6 Correct 432 ms 289424 KB Output is correct
7 Correct 405 ms 70496 KB Output is correct
8 Correct 561 ms 204064 KB Output is correct
9 Correct 585 ms 180732 KB Output is correct
10 Correct 456 ms 178196 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 51304 KB Output is correct
2 Correct 55 ms 50844 KB Output is correct
3 Correct 60 ms 51140 KB Output is correct
4 Correct 60 ms 50324 KB Output is correct
5 Correct 55 ms 50712 KB Output is correct
6 Correct 64 ms 51120 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47392 KB Output is correct
2 Correct 23 ms 47380 KB Output is correct
3 Correct 23 ms 47316 KB Output is correct
4 Correct 24 ms 47384 KB Output is correct
5 Correct 26 ms 47336 KB Output is correct
6 Correct 24 ms 47388 KB Output is correct
7 Correct 25 ms 47316 KB Output is correct
8 Correct 662 ms 259592 KB Output is correct
9 Correct 696 ms 248424 KB Output is correct
10 Correct 643 ms 256420 KB Output is correct
11 Correct 638 ms 246680 KB Output is correct
12 Correct 439 ms 285924 KB Output is correct
13 Correct 432 ms 289424 KB Output is correct
14 Correct 405 ms 70496 KB Output is correct
15 Correct 561 ms 204064 KB Output is correct
16 Correct 585 ms 180732 KB Output is correct
17 Correct 456 ms 178196 KB Output is correct
18 Correct 71 ms 51304 KB Output is correct
19 Correct 55 ms 50844 KB Output is correct
20 Correct 60 ms 51140 KB Output is correct
21 Correct 60 ms 50324 KB Output is correct
22 Correct 55 ms 50712 KB Output is correct
23 Correct 64 ms 51120 KB Output is correct
24 Correct 624 ms 223132 KB Output is correct
25 Correct 632 ms 224308 KB Output is correct
26 Correct 616 ms 221228 KB Output is correct
27 Correct 625 ms 221260 KB Output is correct
28 Correct 590 ms 97568 KB Output is correct
29 Correct 307 ms 66092 KB Output is correct