Submission #1297091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297091		NotLinux	Peru (RMI20_peru)	C++20	100 / 100	124 ms	32208 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()

typedef long long ll;

const ll inf = 1e18 + 7;
const ll mod = 1e9 + 7;

struct MinStack{
    stack<pair<ll,ll>>st;
    ll getmin(){
        return st.empty() ? inf : st.top().second;
    }
    void push(ll x){
        st.push({x , min(x , getmin())});
    }
    ll pop(){
        if(!st.empty()){
            ll x = st.top().first;
            st.pop();
            return x;
        }
        else return -1;
    }
    int getsz(){
        return sz(st);
    }
    void swap(MinStack &x){
        st.swap(x.st);
    }
};

struct MinDeque{
    MinStack s1 , s2 , s3;
    ll getmin(){
        return min(s1.getmin() , s2.getmin());
    }
    void push_front(ll x){
        s1.push(x);
    }
    void push_back(ll x){
        s2.push(x);
    }
    ll pop_front(){
        if(s1.getsz() == 0){
            int len = s2.getsz();
            for(int i = 0;i<len / 2;i++){
                s3.push(s2.pop());
            }
            while(s2.getsz()){
                s1.push(s2.pop());
            }
            while(s3.getsz()){
                s2.push(s3.pop());
            }
        }
        return s1.pop();
    }
    ll pop_back(){
        if(s2.getsz() == 0){
            int len = s1.getsz();
            for(int i = 0;i<len / 2;i++){
                s3.push(s1.pop());
            }
            while(s1.getsz()){
                s2.push(s1.pop());
            }
            while(s3.getsz()){
                s1.push(s3.pop());
            }
        }
        return s2.pop();
    }
};
signed solve(signed n, signed k, signed* arr){
    deque<pair<int,ll>>dq;// i , dp[prev] + arr[i]
    MinDeque mdq;

    ll dp[n];
    ll maxi = 0;
    for(int i = 0;i<n;i++){
        dp[i] = arr[i] + (i == 0 ? 0ll : dp[i-1]);

        while(!dq.empty() and i - dq[0].first > k){
            dq.pop_front();
            mdq.pop_front();
        }
        while(!dq.empty() and arr[dq.back().first] < arr[i]){
            if(sz(dq) > 1)
                dp[i] = min(dp[i] , dq.back().second - arr[dq.back().first] + arr[i]);
            dq.pop_back();
            mdq.pop_back();
        }

        ll x = mdq.pop_front();
        dp[i] = min(dp[i] , mdq.getmin());

        if(!dq.empty()){
            dp[i] = min(dp[i] , arr[dq[0].first] + dp[max(0 , i-k)]);
        }
        else{
            dp[i] = min(dp[i] , arr[i] + dp[max(0 , i-k)]);
        }

        if(x != -1)mdq.push_front(x);

        // cout << i << " : ";for(auto itr : dq)cout << itr.first << "," << itr.second << "   ";cout << endl;
        maxi = max(maxi , (ll)arr[i]);
        if(i < k){
            dp[i] = min(dp[i] , (ll)maxi);
        }
        // cout << endl;
        ll prevdp = 0;
        if(!dq.empty()){
            prevdp = dp[dq.back().first];
        }
        dq.push_back({i , prevdp + arr[i]});
        mdq.push_back(prevdp + arr[i]);
    }
    ll ans = 0 , kat = 1;
    for(int i = n-1;i>=0;i--){
        dp[i] %= mod;
        kat %= mod;
        // cout << "+= " << dp[i] << " * " << kat << endl;
        ll val = (dp[i] * kat) % mod;
        // cout << "val : " << val << endl;
        ans = (ans + val) % mod;
        kat = kat * 23ll % mod;
    }
    return ans;
}

// signed main(){
//     int n,k;
//     cin >> n >> k;
//     int arr[n];
//     for(int i = 0;i<n;i++)cin >> arr[i];
//     cout << solve(n,k,arr) << endl;
// }

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