oj.uz

Submission #642709

# Submission time Handle Problem Language Result Execution time Memory
642709 2022-09-20T12:03:11 Z Tenis0206 Peru (RMI20_peru) C++17
49 / 100
 239 ms 30460 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, 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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 212 ms 23016 KB Output is correct
16 Correct 225 ms 27228 KB Output is correct
17 Correct 210 ms 27056 KB Output is correct
18 Correct 222 ms 27164 KB Output is correct
19 Correct 234 ms 27172 KB Output is correct
20 Correct 226 ms 27116 KB Output is correct
21 Correct 238 ms 27136 KB Output is correct
22 Correct 224 ms 26868 KB Output is correct
23 Correct 232 ms 26864 KB Output is correct
24 Correct 222 ms 26712 KB Output is correct
25 Correct 216 ms 26832 KB Output is correct
26 Correct 212 ms 27100 KB Output is correct
27 Correct 221 ms 27096 KB Output is correct
28 Correct 215 ms 27140 KB Output is correct
29 Correct 239 ms 27204 KB Output is correct
30 Correct 211 ms 27084 KB Output is correct
31 Correct 221 ms 27092 KB Output is correct
32 Correct 220 ms 27216 KB Output is correct
33 Correct 210 ms 27096 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 23016 KB Output is correct
2 Correct 225 ms 27228 KB Output is correct
3 Correct 210 ms 27056 KB Output is correct
4 Correct 222 ms 27164 KB Output is correct
5 Correct 234 ms 27172 KB Output is correct
6 Correct 226 ms 27116 KB Output is correct
7 Correct 238 ms 27136 KB Output is correct
8 Correct 224 ms 26868 KB Output is correct
9 Correct 232 ms 26864 KB Output is correct
10 Correct 222 ms 26712 KB Output is correct
11 Correct 216 ms 26832 KB Output is correct
12 Correct 212 ms 27100 KB Output is correct
13 Correct 221 ms 27096 KB Output is correct
14 Correct 215 ms 27140 KB Output is correct
15 Correct 239 ms 27204 KB Output is correct
16 Correct 211 ms 27084 KB Output is correct
17 Correct 221 ms 27092 KB Output is correct
18 Correct 220 ms 27216 KB Output is correct
19 Correct 210 ms 27096 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 416 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Runtime error 63 ms 30460 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -