oj.uz

Submission #1111677

# Submission time Handle Problem Language Result Execution time Memory
1111677 2024-11-12T15:24:19 Z Zero_OP Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 221 ms 70448 KB 
#include <bits/stdc++.h>

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }

int code(char c){
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'U') return 2;
    if(c == 'C') return 3;
    assert(false);
}

struct Trie{
    struct Node{
        int next[4];
        Node(){
            memset(next, -1, sizeof(next));
        }
    };

    vector<Node> nd;
    Trie() { nd.emplace_back(); }

    int size(){ return (int)nd.size(); }

    void add(const string& s){
        int u = 0;
        for(auto ch : s){
            int c = code(ch);
            if(nd[u].next[c] == -1){
                nd[u].next[c] = size();
                nd.emplace_back();
            }
            u = nd[u].next[c];
        }
    }

    int timer_dfs;
    vector<int> tin, tout;

    void dfsTree(int u){
        tin[u] = ++timer_dfs;
        for(int i = 0; i < 4; ++i){
            if(nd[u].next[i] != -1){
                dfsTree(nd[u].next[i]);
            }
        }
        tout[u] = timer_dfs;
    }

    void construct_tree(){
        timer_dfs = 0;
        tin.resize(size());
        tout.resize(size());
        dfsTree(0);
        assert(timer_dfs == size());
    }

    pair<int, int> get_subtree(int u){
        assert(u < size());
        return make_pair(tin[u], tout[u]);
    }

    int get(const string& s){
        int u = 0;
        for(auto ch : s){
            int c = code(ch);
            if(nd[u].next[c] == -1) return -1;
            u = nd[u].next[c];
        }
        return u;
    }
};

struct Fenwick{
    vector<int> bit;
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int id, int val){
        for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val;
    }

    int query(int l, int r){
        int sum = 0;
        --l;
//        cout << l << ' ' << r << '\n';
        for(; l > 0; l -= l & (-l)) sum -= bit[l];
        for(; r > 0; r -= r & (-r)) sum += bit[r];
        return sum;
    }
};

int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    if(fopen("task.inp", "r")){
//        freopen("task.inp", "r", stdin);
//        freopen("task.out", "w", stdout);
//    }

    int N, Q;
    cin >> N >> Q;
    vector<string> S(N);

    Trie prefix_trie, suffix_trie;
    for(int i = 0; i < N; ++i){
        cin >> S[i];

        prefix_trie.add(S[i]);
        reverse(S[i].begin(), S[i].end());
        suffix_trie.add(S[i]);
    }

    prefix_trie.construct_tree();
    suffix_trie.construct_tree();

    struct event{
        int x, type, l, r, id;
        bool operator < (const event& o){
            return (x == o.x ? type < o.type : x < o.x);
        }
    };

    vector<event> events;

    for(int i = 0; i < N; ++i){

        reverse(S[i].begin(), S[i].end());
        int x = prefix_trie.get(S[i]);

        reverse(S[i].begin(), S[i].end());
        int y = suffix_trie.get(S[i]);

        events.push_back({prefix_trie.tin[x], -1, suffix_trie.tin[y], suffix_trie.tin[y], i});
    }

    vector<int> ans(Q);
    for(int i = 0; i < Q; ++i){
        string p, q;
        cin >> p >> q; reverse(q.begin(), q.end());
        int i1 = prefix_trie.get(p), i2 = suffix_trie.get(q);

        if(i1 == -1 || i2 == -1){
            ans[i] = 0;
            continue;
        }

        int l1, r1, l2, r2;
        tie(l1, r1) = prefix_trie.get_subtree(i1);
        tie(l2, r2) = suffix_trie.get_subtree(i2);

        events.push_back({l1 - 1, 0, l2, r2, i});
        events.push_back({r1, 1, l2, r2, i});
    }

    sort(events.begin(), events.end());

    Fenwick ft(suffix_trie.size());
    for(auto e : events){
        if(e.type == -1){
            ft.update(e.l, +1);
        }
         else{
            if(e.type == 0) ans[e.id] -= ft.query(e.l, e.r);
            else ans[e.id] += ft.query(e.l, e.r);
        }
    }

    for(int i = 0; i < Q; ++i) cout << ans[i] << '\n';

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 59444 KB Output is correct
2 Correct 162 ms 59076 KB Output is correct
3 Correct 170 ms 53620 KB Output is correct
4 Correct 155 ms 51324 KB Output is correct
5 Correct 221 ms 68708 KB Output is correct
6 Correct 217 ms 70448 KB Output is correct
7 Correct 118 ms 8352 KB Output is correct
8 Correct 195 ms 45624 KB Output is correct
9 Correct 191 ms 40800 KB Output is correct
10 Correct 133 ms 36456 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8776 KB Output is correct
2 Correct 28 ms 5324 KB Output is correct
3 Correct 29 ms 5592 KB Output is correct
4 Correct 25 ms 4808 KB Output is correct
5 Correct 24 ms 5080 KB Output is correct
6 Correct 28 ms 5592 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 508 KB Output is correct
8 Correct 201 ms 59444 KB Output is correct
9 Correct 162 ms 59076 KB Output is correct
10 Correct 170 ms 53620 KB Output is correct
11 Correct 155 ms 51324 KB Output is correct
12 Correct 221 ms 68708 KB Output is correct
13 Correct 217 ms 70448 KB Output is correct
14 Correct 118 ms 8352 KB Output is correct
15 Correct 195 ms 45624 KB Output is correct
16 Correct 191 ms 40800 KB Output is correct
17 Correct 133 ms 36456 KB Output is correct
18 Correct 40 ms 8776 KB Output is correct
19 Correct 28 ms 5324 KB Output is correct
20 Correct 29 ms 5592 KB Output is correct
21 Correct 25 ms 4808 KB Output is correct
22 Correct 24 ms 5080 KB Output is correct
23 Correct 28 ms 5592 KB Output is correct
24 Correct 165 ms 53872 KB Output is correct
25 Correct 188 ms 56556 KB Output is correct
26 Correct 164 ms 54320 KB Output is correct
27 Correct 160 ms 49200 KB Output is correct
28 Correct 181 ms 28844 KB Output is correct
29 Correct 118 ms 17332 KB Output is correct