oj.uz

Submission #484496

# Submission time Handle Problem Language Result Execution time Memory
484496 2021-11-03T18:29:00 Z Alexandruabcde Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 115828 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;

int N, M;

string S[NMAX];

int Value (char ch) {
    if (ch == 'A') return 0;
    if (ch == 'C') return 1;
    if (ch == 'G') return 2;
    if (ch == 'U') return 3;
}

struct Node {
    vector <int> ind;
    pair <int, int> p;

    Node *Next[4];

    Node() {
        ind.clear();
        p = {NMAX, -1};
        for (int i = 0; i < 4; ++ i )
            Next[i] = nullptr;
    }
};

Node *TreePref = new Node;
Node *TreeSuf = new Node;

void UpdatePrefix (Node *Tree, string cuv, int val, int Nr_Lit) {
    Tree->p.first = min(Tree->p.first, val);
    Tree->p.second = max(Tree->p.second, val);

    if (Nr_Lit == 0) return;

    int lit = Value(cuv[cuv.size()-Nr_Lit]);

    if (Tree->Next[lit] == nullptr) {
        Tree->Next[lit] = new Node;
    }

    UpdatePrefix(Tree->Next[lit], cuv, val, Nr_Lit-1);
}

void UpdateSuffix (Node *Tree, string cuv, int val, int Nr_Lit) {
    Tree->ind.push_back(val);

    if (Nr_Lit == 0) return;

    int lit = Value(cuv[cuv.size()-Nr_Lit]);

    if (Tree->Next[lit] == nullptr) {
        Tree->Next[lit] = new Node;
    }

    UpdateSuffix(Tree->Next[lit], cuv, val, Nr_Lit-1);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        cin >> S[i];

    sort(S+1, S+N+1);

    for (int i = 1; i <= N; ++ i ) {
        UpdatePrefix(TreePref, S[i], i, S[i].size());

        string aux = S[i];
        reverse(aux.begin(), aux.end());

        UpdateSuffix(TreeSuf, aux, i, aux.size());
    }
}

pair <int, int> AskPrefix (Node *Tree, string P, int Nr_Lit) {
    if (Nr_Lit == 0)
        return Tree->p;

    int lit = Value(P[P.size()-Nr_Lit]);

    if (Tree->Next[lit] == nullptr)
        return {NMAX, -1};

    return AskPrefix(Tree->Next[lit], P, Nr_Lit-1);
}

vector <int> AskSuffix (Node *Tree, string Q, int Nr_Lit) {
    if (Nr_Lit == 0)
        return Tree->ind;

    int lit = Value(Q[Q.size()-Nr_Lit]);

    if (Tree->Next[lit] == nullptr) {
        vector <int> emp;

        return emp;
    }

    return AskSuffix(Tree->Next[lit], Q, Nr_Lit-1);
}

int Query (string Q, int cap_st, int cap_dr) {
    reverse(Q.begin(), Q.end());
    vector <int> aux = AskSuffix(TreeSuf, Q, Q.size());

    vector <int> :: iterator st = lower_bound(aux.begin(), aux.end(), cap_st);
    vector <int> :: iterator dr = upper_bound(aux.begin(), aux.end(), cap_dr);
    dr = prev(dr);

    return (dr - st + 1);
}

void Solve () {
    for (; M; -- M ) {
        string P, Q;

        cin >> P >> Q;

        pair <int, int> per = AskPrefix(TreePref, P, P.size());

        if (per.first > per.second) {
            cout << 0 << '\n';
            continue;
        }

        cout << Query(Q, per.first, per.second) << '\n';
    }
}

int main () {
    Read();

    Solve();

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int Value(char)':
selling_rna.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 4668 KB Output is correct
2 Correct 34 ms 4676 KB Output is correct
3 Correct 46 ms 4608 KB Output is correct
4 Correct 48 ms 4212 KB Output is correct
5 Correct 58 ms 4632 KB Output is correct
6 Correct 83 ms 4584 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Execution timed out 1599 ms 115828 KB Time limit exceeded
9 Halted 0 ms 0 KB -