Submission #494529

#	Time	Username	Problem	Language	Result	Execution time	Memory
494529		leaked	Peru (RMI20_peru)	C++14	0 / 100	79 ms	188240 KiB

peru

#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e6+1;
const int M=1e9+7;
ll dp[N];
ll pw[N];
struct segtree{
    ll t[4*N],p[4*N];
    segtree(){
        fill(t,t+4*N,0);
        fill(p,p+4*N,0);
    }
    void push(int v,int tl,int tr){
        if(tl==tr || !p[v])
            return ;
        for(auto &u : {2*v,2*v+1}){
            t[u]+=p[v];
            p[u]+=p[v];
        }
        p[v]=0;
    }
    void add(int l,int r,ll x,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            t[v]+=x;
            p[v]+=x;
            return;
        }
        if(tl>r||tr<l)
            return ;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        add(l,r,x,2*v,tl,tm);add(l,r,x,2*v+1,tm+1,tr);
        t[v]=min(t[2*v],t[2*v+1]);
    }
    ll get(int l,int r,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            return t[v];
        }
        if(tl>r||tr<l)
            return 1e18;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return min(get(l,r,2*v,tl,tm),get(l,r,2*v+1,tm+1,tr));
    }
}sega;
int solve(int n,int k,int *a){
    int ans=0;
    pw[0]=1;
    for(int i=1;i<n;i++)
        pw[i]=1ll*pw[i-1]*23%M;
    vec<pii>st;
    st.pb({2e9,-1});
    vec<int> lft(n,0);
    for(int i=1;i<=n;i++){
        while(sz(st) && st.back().f<a[i-1]){
            int j=st.back().s;
//            cout<<"A "<<lft[j]<<' '<<j<<endl;
            sega.add(lft[j],j,-a[j],1,0,n);
            st.pop_back();
        }
        lft[i-1]=st.back().s+1;
        st.pb({a[i-1],i-1});
        sega.add(lft[i-1],i-1,a[i-1],1,0,n);
        dp[i]=1e18;
        int mx=-1;
        dp[i]=sega.get(max(0,i-k),i-1,1,0,n);
        sega.add(i,i,dp[i],1,0,n);
//        sega.add(i,i,dp[i]+a[i],1,0,n);
        ans+=1ll*(dp[i]%M)*pw[n-i];
        ans%=M;
//        cout<<dp[i]<<' ';
    }
    return ans;
}
//int a[100];
//signed main(){
//    int n,k;
//    cin>>n>>k;
//    for(int i=0;i<n;i++)
//        cin>>a[i];
//    cout<<solve(n,k,a);
//}

Compilation message (stderr)

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:75:13: warning: unused variable 'mx' [-Wunused-variable]
   75 |         int mx=-1;
      |             ^~

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