#include "peru.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int INF = numeric_limits<int>::max()/2;
int mod = 1e9+7;
struct SegmentTree{
int len = 1;
vector<int> S;
SegmentTree(vector<int> arr){
int n = arr.size();
while(len < n){
len <<= 1;
}
S.resize(2*len);
for(int i = 0; i < n; i++){
S[i+len] = arr[i];
}
for(int i = len-1; i > 0; i--){
S[i] = max(S[i*2], S[i*2+1]);
}
}
int query(int ql, int qr, int l = 0, int r = -2, int i = 1){
if(r == -2) r = len;
if(ql <= l && r <= qr) return S[i];
if(r <= ql || qr <= l) return 0;
int mid = (l+r)/2;
return max(query(ql,qr,l,mid,i*2),query(ql,qr,mid,r,i*2+1));
}
};
int exp(int a, int k){
if(k == 0) return 1;
int res = exp(a,k/2);
if(k % 2 == 0) return (res * res) % mod;
return ((res*res% mod) * a )% mod;
}
int32_t solve(int32_t n, int32_t k, int32_t* S){
vector<int> v(n);
for(int i = 0; i < n; i++){
v[i] = S[i];
}
vector<int> dp(n+1, INF);
dp[0] = 0;
int res = 0;
SegmentTree seg(v);
for(int i = 1; i <= n; i++){
int ma = 0;
int l = max(1LL, i-k+1LL);
int r = i-1;
dp[i] = dp[i-1]+seg.query(i-1, i);
while(l <= r){
int mid = (l+r)/2;
int r1 = dp[mid-1]+seg.query(mid-1, i);
int r2 = dp[mid]+seg.query(mid, i);
dp[i] = min({dp[i], r1,r2});
if(r1-r2 >= 0){
l = mid+1;
}else{
r = mid-1;
}
}
// dp[i] = dp[max(0LL, i-k)];
// int l = max(0LL, i-k);
// ma = seg.query(l, i);
// dp[i] += ma;
res += ((dp[i]%mod) * exp(23, n-i))%mod;
assert(res >= 0);
res %= mod;
}
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |