제출 #858131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
858131		Denkata	Peru (RMI20_peru)	C++14	18 / 100	640 ms	131624 KiB

peru

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51