oj.uz

Submission #858133

# Submission time Handle Problem Language Result Execution time Memory
858133 2023-10-07T12:47:49 Z Denkata Peru (RMI20_peru) C++14
18 / 100
 600 ms 44016 KB 
#include<bits/stdc++.h>
#include "peru.h"
//#include "grader.cpp"
using namespace std;
typedef long long ll;
const int maxn = 4e5+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 7 ms 17148 KB Output is correct
2 Correct 7 ms 16988 KB Output is correct
3 Correct 7 ms 16988 KB Output is correct
4 Correct 9 ms 17148 KB Output is correct
5 Correct 8 ms 16984 KB Output is correct
6 Correct 8 ms 16988 KB Output is correct
7 Correct 7 ms 17152 KB Output is correct
8 Correct 7 ms 17056 KB Output is correct
9 Correct 7 ms 16988 KB Output is correct
10 Correct 8 ms 16988 KB Output is correct
11 Correct 8 ms 16988 KB Output is correct
12 Correct 8 ms 16988 KB Output is correct
13 Correct 8 ms 16988 KB Output is correct
14 Correct 7 ms 16988 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17148 KB Output is correct
2 Correct 7 ms 16988 KB Output is correct
3 Correct 7 ms 16988 KB Output is correct
4 Correct 9 ms 17148 KB Output is correct
5 Correct 8 ms 16984 KB Output is correct
6 Correct 8 ms 16988 KB Output is correct
7 Correct 7 ms 17152 KB Output is correct
8 Correct 7 ms 17056 KB Output is correct
9 Correct 7 ms 16988 KB Output is correct
10 Correct 8 ms 16988 KB Output is correct
11 Correct 8 ms 16988 KB Output is correct
12 Correct 8 ms 16988 KB Output is correct
13 Correct 8 ms 16988 KB Output is correct
14 Correct 7 ms 16988 KB Output is correct
15 Correct 362 ms 39924 KB Output is correct
16 Correct 331 ms 39772 KB Output is correct
17 Correct 268 ms 40024 KB Output is correct
18 Correct 594 ms 39924 KB Output is correct
19 Execution timed out 609 ms 44016 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 39924 KB Output is correct
2 Correct 331 ms 39772 KB Output is correct
3 Correct 268 ms 40024 KB Output is correct
4 Correct 594 ms 39924 KB Output is correct
5 Execution timed out 609 ms 44016 KB Time limit exceeded
6 Halted 0 ms 0 KB -