Submission #1110118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110118		SSKMF	Peru (RMI20_peru)	C++17	100 / 100	117 ms	56824 KiB

peru

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

const int mod(1000000007);
deque < pair <int , int> > candidati;

class Stiva {
private:
    stack < pair <int64_t , int64_t> > minim;
public:
    bool empty () { return minim.empty(); }
    int size () { return (int)minim.size(); }
    void push (int64_t valoare) { minim.push({valoare , (minim.empty() ? valoare : min(valoare , minim.top().second))}); }
    pair <int64_t , int64_t>& top () { return minim.top(); }
    void swap (Stiva &alta) { minim.swap(alta.minim); }
    void pop () { minim.pop(); }
};

class Deque {
private:
    Stiva stanga , dreapta;
    void Rebalance ()
    {
        bool schimbat = false;
        if (schimbat |= dreapta.empty())
            { dreapta.swap(stanga); }

        stack <int64_t> temporar;
        for (int copie = dreapta.size() / 2 ; copie ; copie--)
            { temporar.push(dreapta.top().first); dreapta.pop(); }

        for (int copie = dreapta.size() ; copie ; copie--)
            { stanga.push(dreapta.top().first); dreapta.pop(); }
            
        for (int copie = temporar.size() ; copie ; copie--)
            { dreapta.push(temporar.top()); temporar.pop(); }

        if (schimbat)
            { dreapta.swap(stanga); }
    }
public:
    void pop_front () { if (stanga.empty()) { Rebalance(); } stanga.pop(); }
    void pop_back () { if (dreapta.empty()) { Rebalance(); } dreapta.pop(); }
    void push_back (int64_t valoare) { dreapta.push(valoare); }
    void push_front (int64_t valoare) { stanga.push(valoare); }
    int64_t query () { return min((stanga.empty() ? INT64_MAX : stanga.top().second) , (dreapta.empty() ? INT64_MAX : dreapta.top().second)); }
} __minim;

int64_t minim[2500001];

int solve (int lungime , int limita , int *sir)
{
    int rezultat = 0;
    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        pair <int , int> actual = {sir[indice - 1] , indice};
        while (!candidati.empty() && candidati.back() <= actual)
            { candidati.pop_back(); __minim.pop_back(); }

        __minim.push_back(actual.first + minim[candidati.empty() ? max(0 , indice - limita) : candidati.back().second]);
        candidati.push_back(actual);

        if (candidati.front().second == indice - limita)
            { candidati.pop_front(); __minim.pop_front(); }
        else
        {
            __minim.pop_front();
            __minim.push_front(candidati.front().first + minim[max(0 , indice - limita)]);
        }

        minim[indice] = __minim.query();
        rezultat = (23LL * rezultat + minim[indice]) % mod;
    }

    return rezultat;
}

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