oj.uz

Submission #859773

# Submission time Handle Problem Language Result Execution time Memory
859773 2023-10-10T15:41:12 Z activedeltorre Peru (RMI20_peru) C++14
49 / 100
 600 ms 134032 KB 
#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<long long,long long> >st;
void push_lazy(long long node,long long st,long long dr)
{
    va[node]+=lazy[node];
    if(st!=dr)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void update(long long node,long long st,long long dr,long long qst,long long qdr,long long 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 ;
    }
    long long 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(long long node,long long st,long long dr,long long qst,long long 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];
    }
    long long 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)
{
    long long 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]);
    }
    long long 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*1LL,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 long long s[2500005];
static long long n, k;
signed main(){
    cin>> n >> k;
    for(long long i = 0; i < n; i++){
        cin>> s[i];
    }
    long long ans = solve(n, k, s);
    cout<< ans <<"\n";
    return 0;
}*/

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:57:17: warning: unused variable 'b' [-Wunused-variable]
   57 |     long long a,b,i,val,poz;
      |                 ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6616 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6584 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6668 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6616 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 2 ms 6584 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6668 KB Output is correct
15 Correct 390 ms 37352 KB Output is correct
16 Correct 401 ms 37204 KB Output is correct
17 Correct 376 ms 37520 KB Output is correct
18 Correct 388 ms 37132 KB Output is correct
19 Correct 397 ms 37072 KB Output is correct
20 Correct 393 ms 37204 KB Output is correct
21 Correct 383 ms 37176 KB Output is correct
22 Correct 385 ms 37696 KB Output is correct
23 Correct 392 ms 37780 KB Output is correct
24 Correct 375 ms 37428 KB Output is correct
25 Correct 380 ms 37796 KB Output is correct
26 Correct 378 ms 37568 KB Output is correct
27 Correct 385 ms 37200 KB Output is correct
28 Correct 387 ms 37800 KB Output is correct
29 Correct 383 ms 37204 KB Output is correct
30 Correct 387 ms 37344 KB Output is correct
31 Correct 376 ms 37204 KB Output is correct
32 Correct 392 ms 37396 KB Output is correct
33 Correct 399 ms 37304 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 37352 KB Output is correct
2 Correct 401 ms 37204 KB Output is correct
3 Correct 376 ms 37520 KB Output is correct
4 Correct 388 ms 37132 KB Output is correct
5 Correct 397 ms 37072 KB Output is correct
6 Correct 393 ms 37204 KB Output is correct
7 Correct 383 ms 37176 KB Output is correct
8 Correct 385 ms 37696 KB Output is correct
9 Correct 392 ms 37780 KB Output is correct
10 Correct 375 ms 37428 KB Output is correct
11 Correct 380 ms 37796 KB Output is correct
12 Correct 378 ms 37568 KB Output is correct
13 Correct 385 ms 37200 KB Output is correct
14 Correct 387 ms 37800 KB Output is correct
15 Correct 383 ms 37204 KB Output is correct
16 Correct 387 ms 37344 KB Output is correct
17 Correct 376 ms 37204 KB Output is correct
18 Correct 392 ms 37396 KB Output is correct
19 Correct 399 ms 37304 KB Output is correct
20 Correct 2 ms 6748 KB Output is correct
21 Correct 3 ms 6612 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 2 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 2 ms 6492 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 2 ms 6616 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6584 KB Output is correct
30 Correct 2 ms 6492 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Correct 2 ms 6492 KB Output is correct
33 Correct 2 ms 6668 KB Output is correct
34 Execution timed out 1016 ms 134032 KB Time limit exceeded
35 Halted 0 ms 0 KB -