#include <iostream>
#include <queue>
#include <stack>
#include "peru.h"
using namespace std;
long long lazy[8300005];
long long va[8300005];
int vec[5000005];
//ifstream cin("a.in");
//ofstream cout("a.out");
stack<pair<long long,int> >st;
void push_lazy(int node,int st,int dr)
{
va[node]+=lazy[node];
if(st!=dr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void update(int node,int st,int dr,int qst,int 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 ;
}
int 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]);
}
int querry(int node,int st,int dr,int qst,int 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];
int 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];
int solve(int n, int k, int* v)
{
int a,b,i,poz;
long long val;
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(0,i-k),i-1);
update(1,0,n,i,i,dp[i]);
}
int 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 int s[2500005];
static int n, k;
signed main(){
cin>> n >> k;
for(int i = 0; i < n; i++){
cin>> s[i];
}
int ans = solve(n, k, s);
cout<< ans <<"\n";
return 0;
}*/
Compilation message
peru.cpp: In function 'int querry(int, int, int, int, int)':
peru.cpp:42:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
42 | return 1e18;
| ^~~~
peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:51:11: warning: unused variable 'b' [-Wunused-variable]
51 | int a,b,i,poz;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
