oj.uz

Submission #858131

# Submission time Handle Problem Language Result Execution time Memory
858131 2023-10-07T12:46:26 Z Denkata Peru (RMI20_peru) C++14
18 / 100
 600 ms 131624 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 46 ms 98540 KB Output is correct
2 Correct 48 ms 98288 KB Output is correct
3 Correct 51 ms 98384 KB Output is correct
4 Correct 46 ms 98384 KB Output is correct
5 Correct 44 ms 98392 KB Output is correct
6 Correct 44 ms 98388 KB Output is correct
7 Correct 44 ms 98536 KB Output is correct
8 Correct 45 ms 98388 KB Output is correct
9 Correct 43 ms 98460 KB Output is correct
10 Correct 44 ms 98384 KB Output is correct
11 Correct 45 ms 98568 KB Output is correct
12 Correct 48 ms 98344 KB Output is correct
13 Correct 44 ms 98396 KB Output is correct
14 Correct 46 ms 98384 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98540 KB Output is correct
2 Correct 48 ms 98288 KB Output is correct
3 Correct 51 ms 98384 KB Output is correct
4 Correct 46 ms 98384 KB Output is correct
5 Correct 44 ms 98392 KB Output is correct
6 Correct 44 ms 98388 KB Output is correct
7 Correct 44 ms 98536 KB Output is correct
8 Correct 45 ms 98388 KB Output is correct
9 Correct 43 ms 98460 KB Output is correct
10 Correct 44 ms 98384 KB Output is correct
11 Correct 45 ms 98568 KB Output is correct
12 Correct 48 ms 98344 KB Output is correct
13 Correct 44 ms 98396 KB Output is correct
14 Correct 46 ms 98384 KB Output is correct
15 Correct 402 ms 127312 KB Output is correct
16 Correct 370 ms 131576 KB Output is correct
17 Correct 294 ms 131624 KB Output is correct
18 Execution timed out 640 ms 131416 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 127312 KB Output is correct
2 Correct 370 ms 131576 KB Output is correct
3 Correct 294 ms 131624 KB Output is correct
4 Execution timed out 640 ms 131416 KB Time limit exceeded
5 Halted 0 ms 0 KB -