Submission #1131575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131575		SSKMF	Selling RNA Strands (JOI16_selling_rna)	C++20	100 / 100	108 ms	85404 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

int cantitate = 1 , radacina[2000001];
struct Nod { int aparitii[2] = { } , urmatorul[4] = { }; } arbore_1[5000001];
struct __Nod { int aparitii = 0 , urmatorul[4] = { }; } arbore_2[5000001];
stack < pair <int , int> > stiva;
string sir;

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int lungime , numar_intrebari;
    cin >> lungime >> numar_intrebari;

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        cin >> sir;

        int nod = 1;
        for (auto& valoare : sir)
        {
            arbore_1[nod].aparitii[0]++;
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            if (!arbore_1[nod].urmatorul[__urmatorul])
                { arbore_1[nod].urmatorul[__urmatorul] = ++cantitate; }

            nod = arbore_1[nod].urmatorul[__urmatorul];
        }

        arbore_1[nod].aparitii[0]++;
        arbore_1[nod].aparitii[1]++;
    }

    stiva.push({1 , 0});
    sir.resize(100001);

    cantitate = 0;
{   int __indice = 0;
    while (!stiva.empty())
    {
        const int nod_actual = stiva.top().first;
        while (stiva.top().second < 4)
        {
            if (arbore_1[nod_actual].urmatorul[stiva.top().second])
            {
                sir[stiva.size() - 1] = ((stiva.top().second < 2 ? (stiva.top().second == 0 ? 'A' : 'U') : (stiva.top().second == 2 ? 'G' : 'C')));
                
                const int nod_vecin = arbore_1[nod_actual].urmatorul[stiva.top().second++];
                for (int indice = 1 ; indice <= arbore_1[nod_vecin].aparitii[1] ; indice++)
                { 
                    __indice++; 

                    int nod_1 = radacina[__indice - 1] , nod_2 = (radacina[__indice] = ++cantitate);
                    for (int indice = (int)stiva.size() - 1 ; indice >= 0 ; indice--)
                    {
                        const int __urmatorul = (sir[indice] == 'A' || sir[indice] == 'U' ? (sir[indice] == 'A' ? 0 : 1) : (sir[indice] == 'G' ? 2 : 3));

                        arbore_2[nod_2] = arbore_2[nod_1];
                        arbore_2[nod_2].aparitii++;

                        arbore_2[nod_2].urmatorul[__urmatorul] = ++cantitate;
                        nod_1 = arbore_2[nod_1].urmatorul[__urmatorul];
                        nod_2 = arbore_2[nod_2].urmatorul[__urmatorul];
                    }
                    
                    arbore_2[nod_2] = arbore_2[nod_1];
                    arbore_2[nod_2].aparitii++;
                }

                stiva.push({nod_vecin , 0});
                break;
            }

            stiva.top().second++;
        }

        if (stiva.top().second == 4)
            { stiva.pop(); }
    }
}
    while (numar_intrebari--)
    {
        cin >> sir;

        int nod = 1 , anterior = 0;
        for (auto& valoare : sir)
        {
            anterior += arbore_1[nod].aparitii[1];
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            for (int __indice = 0 ; __indice < __urmatorul ; __indice++)
                { anterior += arbore_1[arbore_1[nod].urmatorul[__indice]].aparitii[0]; }

            if (!(nod = arbore_1[nod].urmatorul[__urmatorul]))
                { break; }
        }
        
        cin >> sir;
        
        reverse(sir.begin() , sir.end());
        
        int nod_1 = radacina[anterior] , nod_2 = radacina[anterior + arbore_1[nod].aparitii[0]];
        for (auto &valoare : sir)
        {
            const int __urmatorul = ((valoare == 'A' || valoare == 'U') ? (valoare == 'A' ? 0 : 1) : (valoare == 'G' ? 2 : 3));
            nod_1 = arbore_2[nod_1].urmatorul[__urmatorul];
            nod_2 = arbore_2[nod_2].urmatorul[__urmatorul];
        }
        
        cout << arbore_2[nod_2].aparitii - arbore_2[nod_1].aparitii << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40