#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,mmx")
#include "peru.h"
using namespace std;
#define int long long
using namespace std;
int mod=1000000007;
int n, k, a[2500005], dp[2500005], ax[2500005];
int ll=1, rr=0;
int smh[2500005];
const int N = 2500005;
int t[2 * N];
void build()
{
for (int i = n - 1; i > 0; --i) t[i] = 100000000000000000ll;
}
void modify(int p, int value)
{
// cout<<"concac "<<p<<" "<<value<<endl;
for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = min(t[p],t[p^1]);
}
int query(int l, int r)
{
int res = 100000000000000000ll;
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if (l&1) res = min(res, t[l++]);
if (r&1) res = min(res, t[--r]);
}
return res;
}
void addto(int pos)
{
while(rr>=ll&&a[pos]>a[smh[rr]])
{
ax[smh[rr]]=100000000000000000ll;
modify(smh[rr], ax[smh[rr]]);
rr--;
}
if(rr>=ll)
{
ax[pos]=a[pos]+dp[smh[rr]];
modify(pos, ax[pos]);
// lol.push({-ax[pos], pos});
}
else
{
ax[pos]=a[pos]+dp[max(0ll, pos-k)];
modify(pos, ax[pos]);
// lol.push({-ax[pos], pos});
}
rr++; smh[rr]=pos;
if(smh[ll]==pos-k)
{
modify(smh[ll], 100000000000000000ll);
ll++;
}
else
{
ax[smh[ll]]=a[smh[ll]]+dp[max(0ll, pos-k)];
modify(smh[ll], ax[smh[ll]]);
// lol.push({-ax[smh[l]], smh[l]});
}
}
signed solve(signed nn, signed kk, int* bucac)
{
n=nn, k=kk;
build();
for(int i=1; i<=n; i++)
{
a[i]=bucac[i-1];
}
for(int i=1; i<=n; i++)
{
addto(i);
dp[i]=query(max(1ll, i-k+1), i+1);
// cout<<i<<" cac"<<endl;
// for(int j=max(1ll, i-k); j<=i; j++)
// {
// cout<<ax[j]<<" ";
// }
// cout<<endl<<dp[i]<<endl;
}
int dhs=1, ans=0;
for(int i=n; i>=1; i--)
{
ans+=(dp[i]%mod*dhs)%mod;
ans%=mod;
dhs=(dhs*23)%mod;
}
return ans;
}
// vector<int> aa={3, 2, 9, 8, 7, 11, 3, 4};
// signed main()
// {
// // n=100;
// // build();
// // modify(2, 5);
// // modify(3, 7);
// // modify(4, 9);
// // modify(2, 7);
// // cout<<query(2, 5);
// // return 0;
// cout<<solve(8, 3, aa);
// }
Compilation message
/usr/bin/ld: /tmp/ccXotUiR.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status
