Submission #859756

# Submission time Handle Problem Language Result Execution time Memory
859756 2023-10-10T15:23:47 Z activedeltorre Peru (RMI20_peru) C++14
0 / 100
2 ms 6492 KB
#include <iostream>
#include <queue>
#include <stack>
#include "peru.h"
using namespace std;
long long lazy[8300005];
long long va[8300005];
int vec[5000005];
//ifstream cin("a.in");
//ofstream cout("a.out");
stack<pair<int,int> >st;
void push_lazy(int node,int st,int dr)
{
    va[node]+=lazy[node];
    if(st!=dr)
    {
        lazy[node*2]+=lazy[node];
        lazy[node*2+1]+=lazy[node];
    }
    lazy[node]=0;
}
void update(int node,int st,int dr,int qst,int qdr,int 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 ;
    }
    int 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(int node,int st,int dr,int qst,int qdr)
{
    push_lazy(node,st,dr);
    if(st>dr || st>qdr || qst>dr || qst>qdr)
    {
        return 1e9;
    }
    if(qst<=st && dr<=qdr)
    {
        return va[node];
    }
    int 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[250005];
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({1e10,-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+1,poz,-val);
        }
        update(1,0,n,st.top().second+1,i,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]);
    }
    int maxim=0;
    dp[n+1]=1e18;
    for(i=n;i>=n-k+1;i--)
    {
        maxim=max(maxim,vec[i]);
        dp[n+1]=min(dp[n+1],dp[i]+maxim);
    }
    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 int s[2500005];
static int n, k;
int main(){
    cin>> n >> k;
    for(int i = 0; i < n; i++){
        cin>> s[i];
    }
    int 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;
      |                 ^
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -