Submission #1110109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110109		SSKMF	Peru (RMI20_peru)	C++17	0 / 100	1 ms	2384 KiB

peru

const int mod(1000000007);
long long temporar[2500002] , *minim = temporar + 1;
int candidati[2500001];

int solve (int lungime , int limita , int *sir)
{
    int rezultat = 0 , stanga = 1 , dreapta = 0;
    for (int indice = 0 ; indice < lungime ; indice++)
    {
        while (stanga <= dreapta && sir[candidati[dreapta]] <= sir[indice])
            { dreapta--; }

        candidati[++dreapta] = indice;
        if (candidati[stanga] == indice - limita)
            { stanga++; }

        int __stanga = stanga , __dreapta = dreapta - 1;
        while (__dreapta - __stanga > 1)
        {
            const int mijloc = (__stanga + __dreapta) >> 1;
            if (sir[candidati[mijloc]] + (mijloc == stanga ? minim[indice - limita] : minim[candidati[mijloc - 1]]) >= sir[candidati[mijloc + 1]] + minim[candidati[mijloc]])
                { __stanga = mijloc; }
            else
                { __dreapta = mijloc; }
        }

        if (__stanga < __dreapta && sir[candidati[__stanga]] + (__stanga == stanga ? minim[indice - limita] : minim[candidati[__stanga - 1]]) >= sir[candidati[__dreapta]] + minim[candidati[__stanga]])
            { __stanga++; }
        
        minim[indice] = sir[candidati[__stanga]] + (__stanga == stanga ? minim[indice - limita] : minim[candidati[__stanga - 1]]);
        rezultat = (23LL * rezultat + minim[indice]) % mod;
    }

    return rezultat;
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51