oj.uz

Submission #710594

# Submission time Handle Problem Language Result Execution time Memory
710594 2023-03-15T11:54:37 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++14
0 / 100
 1500 ms 168876 KB 
#include <bits/stdc++.h>
using namespace std;

#define tcT template<class T
#define each(e, a) for(auto &(e) : (a))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int)(v).size()
#define nl '\n';

using ll = long long;
tcT> bool ckmin(T&a, const T&b) { return b < a ? a = b, 1 : 0; }
tcT> bool ckmax(T&a, const T&b) { return b > a ? a = b, 1 : 0; }

const ll INF = 1e18; const int MOD = 1e9 + 7;

const int MX = 1e5+5;

struct Trie {
    vector<array<int,4>> nex = {{{}}};
    vector<vector<int>> lst = {{}};
    vector<int> cnt = {0};
    void ins(const string&s, int ind) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            char c = s[i];
            if(!nex[cur][c]) {
                nex[cur][c] = sz(nex);
                nex.push_back({{{}}});
                lst.push_back({});
                cnt.push_back(0);
            }
            cur = nex[cur][c];
            lst[cur].push_back(ind);
        }
        cnt[cur]++;
    }
    void dfs(int u, string&cur, vector<string>& anslst) {
        for(int i = 0; i < cnt[u]; i++) {
            anslst.push_back(cur);
        }

        for(int i = 0; i < 4; i++) {
            if(nex[u][i]) {
                cur += char(i);
                dfs(nex[u][i], cur, anslst);
                cur.pop_back();
            }
        }
    }

    pair<int,int> getlr(const string&s) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            int c = s[i];
            if(!nex[cur][c]) return {-1, -1};
            cur = nex[cur][c];
        }
        sort(all(lst[cur]));
        return {*lst[cur].begin(), *lst[cur].rbegin()};
    }

    int get_cnt(const string&s, int l, int r) {
        int cur = 0;
        for(int i = 0; i < sz(s); i++) {
            int c = s[i];
            if(!nex[cur][c]) return 0;
            cur = nex[cur][c];
        }
        return upper_bound(all(lst[cur]), r) - lower_bound(all(lst[cur]), l);
    }
};

int N, M;
string s[MX];

void sort_all() {
    Trie trie;
    for(int i = 0; i < N; i++) {
        trie.ins(s[i], i);
    }
    vector<string> lst;
    string cur = "";
    trie.dfs(0, cur, lst);
    for(int i = 0; i < N; i++) s[i] = lst[i];
}

char getid(char c) {
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'C') return 2;
    return 3;
}

void solve() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        cin >> s[i];
        for(int j = 0; j < sz(s[i]); j++) {
            s[i][j] = getid(s[i][j]);
        }
    }
    sort_all();

    Trie trie1;
    for(int i = 0; i < N; i++) {
        trie1.ins(s[i], i);
        reverse(all(s[i]));
    }

    Trie trie2;
    for(int i = 0; i < N; i++) {
        trie2.ins(s[i], i);
    }

    while(M-- > 0) {
        string P, Q;
        cin >> P >> Q;
        for(int i = 0; i < sz(P); i++) {
            P[i] = getid(P[i]);
        }
        for(int i = 0; i < sz(Q); i++) Q[i] = getid(Q[i]);
        int l, r; tie(l, r) = trie1.getlr(P);
        if(~l) { cout << trie2.get_cnt(Q, l, r) << nl; }
        else cout << "0\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 288 ms 168876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 6472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -