Submission #859782

#	Time	Username	Problem	Language	Result	Execution time	Memory
859782		activedeltorre	Peru (RMI20_peru)	C++14	49 / 100	1046 ms	108456 KiB

peru

#include <iostream>
#include <queue>
#include <stack>
#include "peru.h"
#pragma GCC optimize(" unroll-loops")
#pragma GCC optimization("O3")
using namespace std;
long long lazy[8300005];
long long va[8300005];
int vec[5000005];
//ifstream cin("a.in");
//ofstream cout("a.out");
stack<pair<long long,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,long long 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 1e18;
    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[2500005];
int solve(int n, int k, int* v)
{
    int a,b,i,poz;
    long long val;
    for(i=1;i<=n;i++)
    {
        vec[i]=v[i-1];
    }
    st.push({1e18,-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,poz-1,-val);
        }
        update(1,0,n,st.top().second,i-1,a);
        st.push({a,i});
        dp[i]=querry(1,0,n,max(0,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--)
    {
        dp[n+1]=min(dp[n+1],dp[i]+maxim);
        maxim=max(maxim,vec[i]);
    }
    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;
signed 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 (stderr)

peru.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization("O3")
      | 
peru.cpp:5:37: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    5 | #pragma GCC optimize(" unroll-loops")
      |                                     ^
peru.cpp:14:38: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   14 | void push_lazy(int node,int st,int dr)
      |                                      ^
peru.cpp:24:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   24 | void update(int node,int st,int dr,int qst,int qdr,long long val)
      |                                                                 ^
peru.cpp:40:56: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   40 | long long querry(int node,int st,int dr,int qst,int qdr)
      |                                                        ^
peru.cpp:51:31: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   51 | int solve(int n, int k, int* v)
      |                               ^
peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:53:11: warning: unused variable 'b' [-Wunused-variable]
   53 |     int a,b,i,poz;
      |           ^

• Subtask 1: 18 / 18
• Subtask 2: 31 / 31
• Subtask 3: 0 / 51