oj.uz

Submission #642710

# Submission time Handle Problem Language Result Execution time Memory
642710 2022-09-20T12:04:01 Z Tenis0206 Peru (RMI20_peru) C++14
49 / 100
 600 ms 115096 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[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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 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 2 ms 340 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 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 234 ms 23152 KB Output is correct
16 Correct 224 ms 23080 KB Output is correct
17 Correct 207 ms 23052 KB Output is correct
18 Correct 225 ms 23144 KB Output is correct
19 Correct 223 ms 23052 KB Output is correct
20 Correct 224 ms 23028 KB Output is correct
21 Correct 243 ms 23104 KB Output is correct
22 Correct 222 ms 22776 KB Output is correct
23 Correct 216 ms 22744 KB Output is correct
24 Correct 252 ms 22704 KB Output is correct
25 Correct 214 ms 22760 KB Output is correct
26 Correct 214 ms 23036 KB Output is correct
27 Correct 280 ms 23084 KB Output is correct
28 Correct 244 ms 23088 KB Output is correct
29 Correct 241 ms 23008 KB Output is correct
30 Correct 233 ms 22984 KB Output is correct
31 Correct 219 ms 22956 KB Output is correct
32 Correct 262 ms 23080 KB Output is correct
33 Correct 215 ms 22964 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 23152 KB Output is correct
2 Correct 224 ms 23080 KB Output is correct
3 Correct 207 ms 23052 KB Output is correct
4 Correct 225 ms 23144 KB Output is correct
5 Correct 223 ms 23052 KB Output is correct
6 Correct 224 ms 23028 KB Output is correct
7 Correct 243 ms 23104 KB Output is correct
8 Correct 222 ms 22776 KB Output is correct
9 Correct 216 ms 22744 KB Output is correct
10 Correct 252 ms 22704 KB Output is correct
11 Correct 214 ms 22760 KB Output is correct
12 Correct 214 ms 23036 KB Output is correct
13 Correct 280 ms 23084 KB Output is correct
14 Correct 244 ms 23088 KB Output is correct
15 Correct 241 ms 23008 KB Output is correct
16 Correct 233 ms 22984 KB Output is correct
17 Correct 219 ms 22956 KB Output is correct
18 Correct 262 ms 23080 KB Output is correct
19 Correct 215 ms 22964 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 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 Execution timed out 1103 ms 115096 KB Time limit exceeded
35 Halted 0 ms 0 KB -