#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
const ll base = 23;
const ll inf_ll = mod * 2ll * mod + 69ll;
const int MX = 2500005;
ll pwbase[MX];
int n, k, v[MX];
ll dp[MX];
struct dt{
int id;
ll dp_id, dp_min;
};
deque<dt> dq;
int vv = 0;
void pop_front(){
if(dq.size()) dq.pop_front();
if(dq.size()){
ll dp_i = dq.front().dp_id;
dq.front().dp_id = inf_ll;
dq.front().dp_min = inf_ll;
for(int i = 1; i < dq.size(); i ++){
if(dq[i].dp_id <= dp_i) break;
vv ++;
dq[i].dp_min = min(dq[i - 1].dp_min, dq[i].dp_id);
}
}
}
void push_back(int id){
if(dq.empty()){
dq.push_back((dt){id, inf_ll, inf_ll});
return;
}
ll bf = dp[dq.back().id];
dq.push_back((dt){id, bf + v[id], min(bf + v[id], dq.back().dp_min)});
return;
}
int solve(int N, int K, int* V){
n = N; k = K;
for(int i = 0; i < n; i ++) v[i] = V[i];
for(int i = 0; i < n; i ++){
if(dq.size() && i - dq.front().id >= k) pop_front();
while(dq.size() && v[i] >= v[dq.back().id]) dq.pop_back();
push_back(i);
dp[i] = (ll)v[dq.front().id];
if(i >= k) dp[i] += dp[i - k];
if(dq.size())
dp[i] = min(dp[i], dq.back().dp_min);
}
assert(vv <= 2 * n);
pwbase[0] = 1ll;
for(int i = 1; i < n; i ++)
pwbase[i] = (pwbase[i - 1] * 1ll * base) % mod;
ll ans = 0ll;
for(int i = 0; i < n; i ++){
dp[i] %= mod;
(ans += (pwbase[n - 1 - i] * 1ll * dp[i]) % mod) %= mod;
}
return ans;
}
Comp
Compilation message
peru.cpp: In function 'void pop_front()':
peru.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<dt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 1; i < dq.size(); i ++){
| ~~^~~~~~~~~~~
peru.cpp: At global scope:
peru.cpp:78:1: error: 'Comp' does not name a type
78 | Comp
| ^~~~
