oj.uz

Submission #484492

# Submission time Handle Problem Language Result Execution time Memory
484492 2021-11-03T18:12:10 Z Alexandruabcde Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 145004 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;

    Node *Next[4];

    Node() {
        ind.clear();

        for (int i = 0; i < 4; ++ i )
            Next[i] = nullptr;
    }
};

Node *Tree = new Node;

void Update (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;
    }

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

int Compare (string Big, string P) {
    if (Big.size() < P.size()) {
        for (int i = 0; i < Big.size(); ++ i ) {
            if (Big[i] == P[i]) continue;

            if (Big[i] > P[i]) return 1;

            if (Big[i] < P[i]) return -1;
        }

        return -1;
    }

    for (int i = 0; i < P.size(); ++ i ) {
        if (Big[i] == P[i]) continue;

        if (Big[i] > P[i]) return 1;

        if (Big[i] < P[i]) return -1;
    }

    return 0;
}

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 ) {
        string aux = S[i];
        reverse(aux.begin(), aux.end());

        Update(Tree, aux, i, aux.size());
    }
}

vector <int> Ask (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 Ask(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 = Ask(Tree, 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;
        int st = 1, dr = N;
        int ans_st = 0;
        int ans_dr = -1;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            int aux = Compare(S[mij], P);

            if (aux == 0) {
                ans_st = mij;
                dr = mij - 1;
            }
            else if (aux == 1) dr = mij - 1;
            else st = mij + 1;
        }

        if (ans_st == 0) {
            cout << 0 << '\n';
            continue;
        }

        st = 1, dr = N;
        while (st <= dr) {
            int mij = (st + dr) / 2;
            int aux = Compare(S[mij], P);

            if (aux == 0) {
                ans_dr = mij;
                st = mij + 1;
            }
            else if (aux == 1) dr = mij - 1;
            else st = mij + 1;
        }

        cout << Query(Q, ans_st, ans_dr) << '\n';
    }
}

int main () {
    Read();

    Solve();

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int Compare(std::string, std::string)':
selling_rna.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < Big.size(); ++ i ) {
      |                         ~~^~~~~~~~~~~~
selling_rna.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < P.size(); ++ i ) {
      |                     ~~^~~~~~~~~~
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 3440 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 3460 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 1580 ms 145004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 5128 KB Output is correct
2 Correct 58 ms 5000 KB Output is correct
3 Correct 79 ms 4824 KB Output is correct
4 Correct 73 ms 4668 KB Output is correct
5 Correct 83 ms 4680 KB Output is correct
6 Correct 124 ms 4828 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 3440 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 3460 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Execution timed out 1580 ms 145004 KB Time limit exceeded
9 Halted 0 ms 0 KB -