oj.uz

Submission #1110114

# Submission time Handle Problem Language Result Execution time Memory
1110114 2024-11-08T18:29:27 Z SSKMF Peru (RMI20_peru) C++17
0 / 100
 1 ms 2384 KB 
#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 pop () { minim.pop(); }
    void swap (Stiva &alta) { minim.swap(alta.minim); }
};

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

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

        for (int copie = (temporar.size() + 1) / 2 ; copie ; copie--)
            { stanga.push(temporar.top().first); temporar.pop(); }
            
        for (int copie = temporar.size() ; copie ; copie--)
            { dreapta.push(temporar.top().first); 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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -