제출 #484496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484496		Alexandruabcde	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1599 ms	115828 KiB

selling_rna

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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