oj.uz

Submission #858132

# Submission time Handle Problem Language Result Execution time Memory
858132 2023-10-07T12:47:18 Z Denkata Peru (RMI20_peru) C++14
18 / 100
 600 ms 127580 KB 
#include<bits/stdc++.h>
#include "peru.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 3e6+3;
const ll mod = 1e9+7;
ll d[4*maxn],lz[4*maxn];
int nn;
void push_lazy(int p,int l,int r)
{
    if(lz[p]==LLONG_MAX)
        return ;
    d[p] = min(d[p],lz[p]);
    //cout<<p<<" "<<l<<" "<<r<<" "<<d[p]<<endl;
    if(l!=r)
        lz[p*2]=min(lz[p*2],lz[p]);
    if(l!=r)
        lz[p*2+1]=min(lz[p*2+1],lz[p]);
    lz[p] = LLONG_MAX;
}
ll query(int pos,int p=1,int l=1,int r=nn)
{
    push_lazy(p,l,r);
    if(pos==l && pos==r)
        return d[p];
    if(pos<=(l+r)/2)
        return query(pos,p*2,l,(l+r)/2);
    return query(pos,p*2+1,(l+r)/2+1,r);
}

void upd(int ql,int qr,ll val,int p=1,int l=1,int r=nn)
{
    if(ql<ql)return ;
    //cout<<ql<<" "<<qr<<" "<<val<<endl;
    push_lazy(p,l,r);
    if(l>qr || r<ql)
        return ;
    if(l>=ql && r<=qr)
    {
        lz[p] = val;
        push_lazy(p,l,r);
        return ;
    }
    upd(ql,qr,val,p*2,(l),(l+r)/2);
    upd(ql,qr,val,p*2+1,(l+r)/2+1,r);
}
int solve(int N,int K,int *S)
{
    ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
    int otg;
    ll st[maxn];
    ///experiment of the dp with naive approach
    nn = N;
    n = nn;
    for(i=0;i<=4*nn;i++)
        lz[i] = d[i] = LLONG_MAX;
    for(i=0;i<n;i++)
        a[i+1] = S[i];
    dp[0] = 0;
    for(i=1;i<=n;i++)
        dp[i] = LLONG_MAX;
    st[n-1] = 1;
    for(i=n-2;i>=0;i--)
        st[i] = (st[i+1]*23)%mod;

    stack <int> s;
    for(i=n;i>=1;i--)
    {
        while(s.empty()==false && a[i]>a[s.top()])
            s.pop();
        if(!s.empty())
            r[i] = s.top();
        else r[i] = n+1;
        s.push(i);
        //cout<<r[i]<<endl;
    }
    for(i=1;i<=n;i++)
    {
        for(j=i-1;j>=max(i-K,0ll);j--)
        {
            /**for(k=i;k<min(r[i],j+K+1);k++)
            {
              //  cout<<j<<" "<<a[i]<<" kum K "<<k<<endl;
                dp[k] = min(dp[k],(dp[j]+a[i]));
            }
            */
            upd(i,min(r[i],j+K+1)-1,dp[j]+a[i]);
            if(a[j]>=a[i])break;
        }
        dp[i] = query(i);
        //cout<<dp[i]<<" dpi "<<endl;
    }

    /**
    for(i=1;i<=n;i++)
    {
        p = a[i];
        for(j=i-1;j>=max(i-K,0ll);j--)
        {
            dp[i] = min((dp[j]+p),dp[i]);
            p = max(p,a[j]);
        }
        //cout<<dp[i]<<" ";
    }
    */
    for(i=1;i<=n;i++)
    {
       // cout<<i<<" "<<st[i-1]<<endl;
        dp[i] = dp[i]%mod;
        ans+=(dp[i]*1ll*st[i-1])%mod;
        ans%=mod;
    }
    otg = ans;
    return otg;
}

Compilation message

peru.cpp: In function 'void upd(int, int, ll, int, int, int)':
peru.cpp:34:10: warning: self-comparison always evaluates to false [-Wtautological-compare]
   34 |     if(ql<ql)return ;
      |        ~~^~~
peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:50:12: warning: unused variable 'p' [-Wunused-variable]
   50 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |            ^
peru.cpp:50:14: warning: unused variable 'q' [-Wunused-variable]
   50 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |              ^
peru.cpp:50:16: warning: unused variable 'm' [-Wunused-variable]
   50 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |                ^
peru.cpp:50:18: warning: unused variable 'k' [-Wunused-variable]
   50 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |                  ^
peru.cpp:50:37: warning: unused variable 'l' [-Wunused-variable]
   50 |     ll i,j,p,q,m,k,n,dp[maxn],ans=0,l[maxn],r[maxn],a[maxn];
      |                                     ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98400 KB Output is correct
2 Correct 47 ms 98492 KB Output is correct
3 Correct 43 ms 98396 KB Output is correct
4 Correct 46 ms 98388 KB Output is correct
5 Correct 45 ms 98388 KB Output is correct
6 Correct 44 ms 98396 KB Output is correct
7 Correct 44 ms 98528 KB Output is correct
8 Correct 46 ms 98540 KB Output is correct
9 Correct 47 ms 98384 KB Output is correct
10 Correct 44 ms 98384 KB Output is correct
11 Correct 44 ms 98388 KB Output is correct
12 Correct 44 ms 98464 KB Output is correct
13 Correct 44 ms 98384 KB Output is correct
14 Correct 48 ms 98516 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98400 KB Output is correct
2 Correct 47 ms 98492 KB Output is correct
3 Correct 43 ms 98396 KB Output is correct
4 Correct 46 ms 98388 KB Output is correct
5 Correct 45 ms 98388 KB Output is correct
6 Correct 44 ms 98396 KB Output is correct
7 Correct 44 ms 98528 KB Output is correct
8 Correct 46 ms 98540 KB Output is correct
9 Correct 47 ms 98384 KB Output is correct
10 Correct 44 ms 98384 KB Output is correct
11 Correct 44 ms 98388 KB Output is correct
12 Correct 44 ms 98464 KB Output is correct
13 Correct 44 ms 98384 KB Output is correct
14 Correct 48 ms 98516 KB Output is correct
15 Correct 405 ms 127580 KB Output is correct
16 Correct 372 ms 127488 KB Output is correct
17 Correct 293 ms 127488 KB Output is correct
18 Execution timed out 662 ms 127484 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 127580 KB Output is correct
2 Correct 372 ms 127488 KB Output is correct
3 Correct 293 ms 127488 KB Output is correct
4 Execution timed out 662 ms 127484 KB Time limit exceeded
5 Halted 0 ms 0 KB -