#include<bits/stdc++.h>
#include "peru.h"
#define f first
#define s second
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const int N = 4e5 + 5, mod = 1e9 + 7;
ll lazy[4 * N], tree[4 * N], k, n, p[N], dp[N];
void push(int u,int l,int r) {
if(!lazy[u]) return;
tree[u] += lazy[u];
if(l != r) {
lazy[2 * u] += lazy[u];
lazy[2 * u + 1] += lazy[u];
}
lazy[u] = 0;
}
void upd(int u,int st,int en,int l,int r,int val) {
push(u, l, r);
if(l > en || r < st) return;
if(st <= l && r <= en) {
lazy[u] = val;
push(u, l, r);
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, val); upd(2 * u + 1, st, en, mid + 1, r, val);
tree[u] = min(tree[2 * u], tree[2 * u + 1]);
}
ll get(int u,int st,int en, int l,int r) {
push(u, l, r);
if(l > en || r < st) return 1e18;
if(st <= l && r <= en) return tree[u];
int mid = (l + r) / 2;
return min(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
int solve(int n, int k, int* v){
stack<pair<int, pii> > st;
vector<int> s(n + 5);
p[0] = 1;
for(int i = 1; i < n; i++) p[i] = p[i - 1] * 23 % mod;
ll ans = 0, mn = 0;
for(int i = 1; i <= n; i++) {
s[i] = v[i - 1]; mn = max(mn, (ll)s[i]);
int l = i;
while(st.size() && st.top().f <= s[i]) {
l = st.top().s.f;
upd(1, st.top().s.f, st.top().s.s, 0, n, - st.top().f + s[i]);
st.pop();
}
upd(1, i, i, 0, n, dp[i - 1] + s[i]);
dp[i] = get(1, max(1, i - k + 1), i - 1, 0, n);
if(i - k + 1 <= 0) dp[i] = min(dp[i], mn);
st.push({s[i], {l, i}});
ans += p[n- i] * (dp[i] % mod); ans %= mod;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
