oj.uz

Submission #1110117

# Submission time Handle Problem Language Result Execution time Memory
1110117 2024-11-08T18:32:47 Z SSKMF Peru (RMI20_peru) C++17
18 / 100
 600 ms 13044 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 dreapta = 1 ; dreapta <= lungime ; dreapta++)
    {
        minim[dreapta] = INT64_MAX;
        for (int stanga = dreapta , maxim = 0 ; stanga > max(0 , dreapta - limita) ; stanga--)
            { minim[dreapta] = min(minim[dreapta] , minim[stanga - 1] + (maxim = max(maxim , sir[stanga - 1]))); }
    
        rezultat = (23LL * rezultat + minim[dreapta]) % mod;
    }

    return rezultat;
    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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2556 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2556 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 394 ms 12880 KB Output is correct
16 Correct 293 ms 12872 KB Output is correct
17 Correct 180 ms 12872 KB Output is correct
18 Correct 178 ms 13044 KB Output is correct
19 Correct 227 ms 13040 KB Output is correct
20 Correct 450 ms 12872 KB Output is correct
21 Correct 316 ms 12872 KB Output is correct
22 Execution timed out 676 ms 12992 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 12880 KB Output is correct
2 Correct 293 ms 12872 KB Output is correct
3 Correct 180 ms 12872 KB Output is correct
4 Correct 178 ms 13044 KB Output is correct
5 Correct 227 ms 13040 KB Output is correct
6 Correct 450 ms 12872 KB Output is correct
7 Correct 316 ms 12872 KB Output is correct
8 Execution timed out 676 ms 12992 KB Time limit exceeded
9 Halted 0 ms 0 KB -