Submission #1111677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111677		Zero_OP	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	221 ms	70448 KiB

selling_rna

#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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40