Submission #642710

#	Time	Username	Problem	Language	Result	Execution time	Memory
642710		Tenis0206	Peru (RMI20_peru)	C++14	49 / 100	1103 ms	115096 KiB

peru

#include <bits/stdc++.h>

//#define home

#ifndef home

#include "peru.h"

#endif // home

using namespace std;

const long long Mod = 1e9 + 7;

int n,k;
int v[2500005];

long long ai[10000005],lazy[10000005];

long long dp[2500005];

void propag(int nod)
{
    if(lazy[nod]==0)
    {
        return;
    }
    ai[nod*2] += lazy[nod];
    ai[nod*2+1] += lazy[nod];
    lazy[nod*2] += lazy[nod];
    lazy[nod*2+1] += lazy[nod];
    lazy[nod] = 0;
    return;
}

void update(int ua, int ub, long long val, int nod, int a, int b)
{
    if(ua<=a && ub>=b)
    {
        ai[nod] += val;
        lazy[nod] += val;
        return;
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(ua<=mij)
    {
        update(ua,ub,val,nod*2,a,mij);
    }
    if(ub>mij)
    {
        update(ua,ub,val,nod*2+1,mij+1,b);
    }
    ai[nod] = min(ai[nod*2],ai[nod*2+1]);
}

long long query(int qa, int qb, int nod, int a, int b)
{
    if(qa<=a && qb>=b)
    {
        return ai[nod];
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(qa<=mij && qb>mij)
    {
        return min(query(qa,qb,nod*2,a,mij),query(qa,qb,nod*2+1,mij+1,b));
    }
    if(qa<=mij)
    {
        return query(qa,qb,nod*2,a,mij);
    }
    return query(qa,qb,nod*2+1,mij+1,b);
}

int solve(int n, int k, int s[])
{
    for(int i=1;i<=n;i++)
    {
        v[i] = s[i-1];
    }
    stack<int> st;
    st.push(0);
    int Max = 0;
    for(int i=1;i<=n;i++)
    {
        while(st.size() > 1 && v[i] > v[st.top()])
        {
            int last = st.top();
            st.pop();
            update(st.top()+1,last,v[i]-v[last],1,1,n);
        }
        st.push(i);
        update(i,i,dp[i-1]+v[i],1,1,n);
        Max = max(Max,v[i]);
        if(i<=k)
        {
            dp[i] = Max;
        }
        else
        {
            dp[i] = query(i-k+1,i,1,1,n);
        }
    }
    long long rez = 0;
    long long put = 1;
    for(int i=n;i>=1;i--)
    {
        dp[i] %= Mod;
        rez += 1LL * dp[i] * put % Mod;
        rez %= Mod;
        put = 1LL * put * 23 % Mod;
    }
    return rez;
}

#ifdef home

int nn;
int vv[100005];

signed main()
{
    freopen("peru.in","r",stdin);
    freopen("peru.out","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>vv[i];
    }
    cout<<solve(n,k,vv)<<'\n';
    return 0;
}

#endif // home

• Subtask 1: 18 / 18
• Subtask 2: 31 / 31
• Subtask 3: 0 / 51