Tema (versiunea urata)

#include <fstream>
using namespace std;
ifstream cin("tema.in");
ofstream cout("tema.out");
const int mxX = 1e6, mxN = 1e5;
long long v[mxN+1], ciur[mxX+1], primes[mxN], p;
long long frecv[mxX+1];
void build_ciur()
{
    ///Precalculam ciurul.
    ciur[0] = ciur[1] = 1;
    for(int i = 4;i<=mxX;i+=2)
        ciur[i] = 1;
    for(int i = 3;i*i<=mxX;i+=2)
        if(ciur[i]==0)
            for(int j = i*i;j<=mxX;j+=2*i)
                ciur[j] = 1;
    for(int i = 1;i<=mxX;i++)
        if(ciur[i]==0)
            primes[++p] = i;
}
int facMin[mxX+1],facMax[mxX+1];
/// aflam cel mai mic si cel mai mare divizor prim din numere.
void buildFac()
{
    for(int i = 1;i<=p;i++)
        for(int j = primes[i];j<=mxX;j+=primes[i])
        {
            if(facMin[j]==0)
                facMin[j] = primes[i];
            facMax[j] = primes[i];
        }

}
int main()
{
    ///Construim ciurul
    build_ciur();
    ///Citim datele
    long long cerinta, n , k ;
    cin>>cerinta>>n>>k;
    for(int i = 1;i<=n;i++)
            cin>>v[i];
    if(cerinta==1)
    {
        ///Folosim two pointers
        long long sol = 0, compsum = 0, primesum = 0;
        long long stanga = 1;
        for(long long dreapta = 1;dreapta<=n;dreapta++)
        {
            if(v[dreapta]!=1) /// 1 nu afecteaza produsul
            {
                if(ciur[v[dreapta]]==0) /// daca este prim
                    primesum+=v[dreapta];
                else compsum+=v[dreapta]; /// daca este compus
            }
            while(compsum*primesum>k) ///garantam ca solutia este valida
            {
                if(v[stanga]==1) /// nu afecteaza produsul
                    stanga++;
                else if(ciur[v[stanga]] == 0)
                    primesum-=v[stanga++];
                else
                    compsum-=v[stanga++];
            }
            sol=max(sol,dreapta-stanga+1);
        }
        cout<<sol<<'\n';
    }
    if(cerinta==2)
    {
        buildFac(); /// aflam cel mai mic si cel mai mare divizor prim din numere.
        int sol = 0, solStanga = -1, solDreapta = -1;

        /// Trebuie gasita o proprietate care sa fie buna doar pt o secventa valida
        /// si care sa poata fi verificata in O(1).

        /// Un lucru care poate veni in minte este frecventa factorilor primi
        /// prezenti in numerele din secventa. Atunci cel putin unul dintre factori
        /// va avea frecventa egala cu lungimea secventei, daca secventa e valida.
        int stanga = 1;
        for(int dreapta = 1;dreapta<=n;dreapta++)
        {
            if(v[dreapta]==1)
            {
                //yayyyy
                while(stanga<dreapta)
                {
                    if(facMin[v[stanga]]==facMax[v[stanga]])
                        frecv[facMin[v[stanga]]]--,stanga++;
                    else
                    {
                        frecv[facMin[v[stanga]]]--;
                        frecv[facMax[v[stanga]]]--;
                        stanga++;
                    }
                }
                stanga = dreapta+1;
                continue;
            }
            frecv[facMin[v[dreapta]]]++;
            frecv[facMax[v[dreapta]]]++;
            if(facMin[v[dreapta]]==facMax[v[dreapta]]) /// Am adaugat de doua ori la frecventa acelasi factor.
                frecv[facMin[v[dreapta]]]--;
            while(frecv[facMin[v[dreapta]]]<dreapta-stanga+1&&frecv[facMax[v[dreapta]]]<dreapta-stanga+1)
            {
                if(facMin[v[stanga]]==facMax[v[stanga]])
                    frecv[facMin[v[stanga]]]--,stanga++;
                else
                {
                    frecv[facMin[v[stanga]]]--;
                    frecv[facMax[v[stanga]]]--;
                    stanga++;
                }
            }
            if(sol <= dreapta-stanga+1)
            {
                sol = dreapta-stanga+1;
                solStanga = stanga;
                solDreapta = dreapta;
            }

        }
        cout<<solStanga<<' '<<solDreapta;

    }
    return 0;
}