#include <iostream>
#include <queue>
#include <stack>
#include "peru.h"
using namespace std;
long long lazy[8300005];
long long va[8300005];
long long vec[5000005];
//ifstream cin("a.in");
//ofstream cout("a.out");
stack<pair<long long,long long> >st;
void push_lazy(long long node,long long st,long long dr)
{
va[node]+=lazy[node];
if(st!=dr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void update(long long node,long long st,long long dr,long long qst,long long qdr,long long val)
{
push_lazy(node,st,dr);
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return ;
}
if(qst<=st && dr<=qdr)
{
lazy[node]=val;
push_lazy(node,st,dr);
return ;
}
long long mij=(st+dr)/2;
update(node*2,st,mij,qst,qdr,val);
update(node*2+1,mij+1,dr,qst,qdr,val);
va[node]=min(va[node*2],va[node*2+1]);
}
long long querry(long long node,long long st,long long dr,long long qst,long long qdr)
{
push_lazy(node,st,dr);
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return 1e18;
}
if(qst<=st && dr<=qdr)
{
return va[node];
}
long long mij=(st+dr)/2;
return min(querry(node*2,st,mij,qst,qdr),querry(node*2+1,mij+1,dr,qst,qdr));
}
long long dp[2500005];
long long solve(long long n, long long k, long long* v)
{
long long a,b,i,val,poz;
for(i=1;i<=n;i++)
{
vec[i]=v[i-1];
}
st.push({1e18,-1});
for(i=1;i<=n;i++)
{
a=vec[i];
while(a>st.top().first)
{
val=st.top().first;
poz=st.top().second;
st.pop();
update(1,0,n,st.top().second,poz-1,-val);
}
update(1,0,n,st.top().second,i-1,a);
st.push({a,i});
dp[i]=querry(1,0,n,max(0LL,i-k),i-1);
update(1,0,n,i,i,dp[i]);
}
long long maxim=0;
dp[n+1]=1e18;
for(i=n;i>=n-k+1;i--)
{
dp[n+1]=min(dp[n+1],dp[i]+maxim);
maxim=max(maxim,vec[i]);
}
dp[n+2]=1e18;
for(i=n;i>=1;i--)
{
dp[i]=min(dp[i],dp[i+1]);
}
long long suma=0,mod=1000000007;
for(i=1;i<=n;i++)
{
suma=(suma*23+dp[i])%mod;
// cout<<dp[i]<<" ";
}
return suma;
}
/*
//#include "peru.h"
using namespace std;
static long long s[2500005];
static long long n, k;
signed main(){
cin>> n >> k;
for(long long i = 0; i < n; i++){
cin>> s[i];
}
long long ans = solve(n, k, s);
cout<< ans <<"\n";
return 0;
}*/
Compilation message
peru.cpp: In function 'long long int solve(long long int, long long int, long long int*)':
peru.cpp:57:17: warning: unused variable 'b' [-Wunused-variable]
57 | long long a,b,i,val,poz;
| ^
/usr/bin/ld: /tmp/cc25BN93.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status
