제출 #823712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823712		vjudge1	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	718 ms	291916 KiB

selling_rna

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