oj.uz

Submission #642706

# Submission time Handle Problem Language Result Execution time Memory
642706 2022-09-20T11:58:05 Z Tenis0206 Peru (RMI20_peru) C++14
0 / 100
 1 ms 340 KB 
#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[500005];

long long ai[2000005],lazy[2000005];

long long dp[500005];

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, int 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);
    }
    if(qb>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()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>vv[i];
    }
    cout<<solve(n,k,vv)<<'\n';
    return 0;
}

#endif // home

Compilation message

peru.cpp: In function 'long long int query(int, int, int, int, int)':
peru.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -