oj.uz

Submission #823715

# Submission time Handle Problem Language Result Execution time Memory
823715 2023-08-13T02:41:25 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 684 ms 367108 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, que;

        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 -> que.pb(-id);
    }

    void dfs(node* u, int len) {
        ++timer;
        for(auto i:u -> s) st[i][len] = timer;
        for(auto i:u -> que) 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 -> que) enq[i] = timer;
    }


    void dfs2(node* u, int len) {
        for(auto i:u -> s) bit.update(st[i][len], 1);
        for(auto i:u -> que) res[i] += bit.query(stq[i], enq[i]);
        for(auto i:u -> s) 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 22 ms 47316 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 24 ms 47388 KB Output is correct
6 Correct 23 ms 47376 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 321468 KB Output is correct
2 Correct 684 ms 306864 KB Output is correct
3 Correct 670 ms 317356 KB Output is correct
4 Correct 671 ms 304736 KB Output is correct
5 Correct 496 ms 362292 KB Output is correct
6 Correct 511 ms 367108 KB Output is correct
7 Correct 403 ms 70720 KB Output is correct
8 Correct 589 ms 248928 KB Output is correct
9 Correct 609 ms 218340 KB Output is correct
10 Correct 464 ms 214632 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 51424 KB Output is correct
2 Correct 55 ms 50944 KB Output is correct
3 Correct 60 ms 51288 KB Output is correct
4 Correct 59 ms 50344 KB Output is correct
5 Correct 60 ms 50904 KB Output is correct
6 Correct 66 ms 51264 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47316 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 22 ms 47316 KB Output is correct
5 Correct 24 ms 47388 KB Output is correct
6 Correct 23 ms 47376 KB Output is correct
7 Correct 23 ms 47316 KB Output is correct
8 Correct 663 ms 321468 KB Output is correct
9 Correct 684 ms 306864 KB Output is correct
10 Correct 670 ms 317356 KB Output is correct
11 Correct 671 ms 304736 KB Output is correct
12 Correct 496 ms 362292 KB Output is correct
13 Correct 511 ms 367108 KB Output is correct
14 Correct 403 ms 70720 KB Output is correct
15 Correct 589 ms 248928 KB Output is correct
16 Correct 609 ms 218340 KB Output is correct
17 Correct 464 ms 214632 KB Output is correct
18 Correct 70 ms 51424 KB Output is correct
19 Correct 55 ms 50944 KB Output is correct
20 Correct 60 ms 51288 KB Output is correct
21 Correct 59 ms 50344 KB Output is correct
22 Correct 60 ms 50904 KB Output is correct
23 Correct 66 ms 51264 KB Output is correct
24 Correct 664 ms 273468 KB Output is correct
25 Correct 680 ms 274588 KB Output is correct
26 Correct 653 ms 270820 KB Output is correct
27 Correct 653 ms 270860 KB Output is correct
28 Correct 624 ms 104068 KB Output is correct
29 Correct 293 ms 65716 KB Output is correct