| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 859770 | activedeltorre | Peru (RMI20_peru) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <queue>
#include <stack>
#include "peru.h"
using namespace std;
long long lazy[8300005];
long long va[8300005];
long long vec[5000005];
//ifstream cin("a.in");
//ofstream cout("a.out");
stack<pair<int,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,int 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]);
}
long long 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,val,poz;
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(0LL,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;
}*/