#include "peru.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using i64=long long;
const i64 INF=1e18;
const i64 inf=1e9;
const int mod=1e9+7;
const int BASE=23;
int lsb(int x)
{
return x&(-x);
}
int add(int x,int y)
{
return (x+y)%mod;
}
int prod(int x,int y)
{
return (1LL*x*y)%mod;
}
struct Aint
{
int n;
vector<i64>aint,lazy;
void init(int n)
{
this->n=n;
int aint_size=n;
while(aint_size!=lsb(aint_size))
{
aint_size+=lsb(aint_size);
}
aint_size<<=1;
aint.assign(aint_size+1 , 0);
lazy.assign(aint_size+1 , 0);
}
void add(int nod,i64 val)
{
aint[nod]+=val;
lazy[nod]+=val;
}
void push_down(int nod)
{
add(nod<<1 , lazy[nod]);
add(nod<<1|1 , lazy[nod]);
lazy[nod]=0;
}
void update(int nod,int st,int dr,int l,int r,int val) {
if (st > r || dr < l) {
return;
}
if (l <= st && dr <= r)
{
add(nod , val);
return;
}
push_down(nod);
int m=(st+dr)/2;
update(nod<<1,st,m,l,r,val);
update(nod<<1|1,m+1,dr,l,r,val);
aint[nod]=min(aint[nod<<1] , aint[nod<<1|1]);
}
i64 query(int nod,int st,int dr,int l,int r)
{
if (st > r || dr < l) {
return INF;
}
if (l <= st && dr <= r)
{
return aint[nod];
}
push_down(nod);
int m=(st+dr)/2;
return min(query(nod<<1,st,m,l,r) , query(nod<<1|1,m+1,dr,l,r));
}
};
int solve(int n, int k, int* v)
{
vector<int>a(n+2 , 2*inf+1);
for(int i=1;i<=n;i++)
{
a[i]=v[i-1];
}
stack<int>sk;
sk.push(0);
Aint dp;
dp.init(n+1);
dp.update(1,0,n,0,0,a[1]);
int rez=0;
for(int i=1;i<=n;i++)
{
while(a[i]>=a[sk.top()])
{
int r=sk.top()-1;
sk.pop();
int l=sk.top();
dp.update(1,0,n,l,r,a[i]-a[r+1]);
}
i64 val=dp.query(1,0,n,max(i-k , 0LL),i-1);
rez=prod(rez , BASE);
rez=add(rez , val%mod);
dp.update(1,0,n,i,i,val+a[i+1]);
sk.push(i);
}
return rez;
}
Compilation message
/usr/bin/ld: /tmp/cczKHTcE.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status
