oj.uz

Submission #823712

# Submission time Handle Problem Language Result Execution time Memory
823712 2023-08-13T02:31:30 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 718 ms 291916 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 47384 KB Output is correct
2 Correct 24 ms 47292 KB Output is correct
3 Correct 25 ms 47300 KB Output is correct
4 Correct 25 ms 47336 KB Output is correct
5 Correct 28 ms 47396 KB Output is correct
6 Correct 24 ms 47304 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 259640 KB Output is correct
2 Correct 633 ms 248336 KB Output is correct
3 Correct 652 ms 260420 KB Output is correct
4 Correct 678 ms 250676 KB Output is correct
5 Correct 434 ms 288324 KB Output is correct
6 Correct 443 ms 291916 KB Output is correct
7 Correct 408 ms 75940 KB Output is correct
8 Correct 567 ms 209952 KB Output is correct
9 Correct 572 ms 186616 KB Output is correct
10 Correct 458 ms 181512 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 51380 KB Output is correct
2 Correct 62 ms 50808 KB Output is correct
3 Correct 61 ms 51448 KB Output is correct
4 Correct 61 ms 50776 KB Output is correct
5 Correct 54 ms 51188 KB Output is correct
6 Correct 65 ms 51612 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47384 KB Output is correct
2 Correct 24 ms 47292 KB Output is correct
3 Correct 25 ms 47300 KB Output is correct
4 Correct 25 ms 47336 KB Output is correct
5 Correct 28 ms 47396 KB Output is correct
6 Correct 24 ms 47304 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 635 ms 259640 KB Output is correct
9 Correct 633 ms 248336 KB Output is correct
10 Correct 652 ms 260420 KB Output is correct
11 Correct 678 ms 250676 KB Output is correct
12 Correct 434 ms 288324 KB Output is correct
13 Correct 443 ms 291916 KB Output is correct
14 Correct 408 ms 75940 KB Output is correct
15 Correct 567 ms 209952 KB Output is correct
16 Correct 572 ms 186616 KB Output is correct
17 Correct 458 ms 181512 KB Output is correct
18 Correct 74 ms 51380 KB Output is correct
19 Correct 62 ms 50808 KB Output is correct
20 Correct 61 ms 51448 KB Output is correct
21 Correct 61 ms 50776 KB Output is correct
22 Correct 54 ms 51188 KB Output is correct
23 Correct 65 ms 51612 KB Output is correct
24 Correct 718 ms 227168 KB Output is correct
25 Correct 660 ms 228372 KB Output is correct
26 Correct 627 ms 225124 KB Output is correct
27 Correct 635 ms 225204 KB Output is correct
28 Correct 548 ms 101980 KB Output is correct
29 Correct 299 ms 69212 KB Output is correct