#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];
inline 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;
}
Compilation message
/usr/bin/ld: /tmp/ccGwQkCg.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status
