Submission #1223782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223782		12345678	Peru (RMI20_peru)	C++17	100 / 100	157 ms	51660 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod=1e9+7, nx=3e6+5;

ll dp[nx], p[nx];

struct minstack
{
    struct data
    {
        ll h, idx, vl, mn;
        data(ll h, ll idx, ll vl, ll mn): h(h), idx(idx), vl(vl), mn(mn){}
    };
    stack<data> s;
    void push(data x)
    {
        if (s.empty()) s.push(data(x.h, x.idx, x.vl, x.vl));
        else s.push(data(x.h, x.idx, x.vl, min(s.top().mn, x.vl)));        
    }
    void pop() {s.pop();}
    bool empty() {return s.empty();}
    void swap(minstack &o) {s.swap(o.s);}
    data top() {return s.top();}
    int size() {return s.size();}
};

struct mindeque
{
    minstack l, r, tmp;
    void rebalance()
    {
        bool sw=0;
        if (r.empty()) sw=1, l.swap(r);
        int sz=r.size()/2;
        while (sz--) tmp.push(r.top()), r.pop();
        while (!r.empty()) l.push(r.top()), r.pop();
        while (!tmp.empty()) r.push(tmp.top()), tmp.pop();
        if (sw) l.swap(r);
    }
    void push(ll h, ll idx, ll vl)
    {
        r.push(minstack::data(h, idx, vl, 0ll));
    }
    ll getmin()
    {
        if (l.empty()) return r.top().mn;
        if (r.empty()) return l.top().mn;
        return min(l.top().mn, r.top().mn);
    }
    minstack::data front()
    {
        if (l.empty()) rebalance();
        return l.top();
    }
    minstack::data back()
    {
        if (r.empty()) rebalance();
        return r.top();
    }
    void pop_front()
    {
        if (l.empty()) rebalance();
        l.pop();
    }
    void pop_back()
    {
        if (r.empty()) rebalance();
        r.pop();
    }
    bool empty() {return l.empty()&&r.empty();}
} dq;

deque<int> rl;

int solve(int n, int k, int* v){
    ll res=0;
    p[0]=1;
    for (int i=1; i<=n; i++) p[i]=(p[i-1]*23)%mod;
    dq.push(1e18, -1, v[0]);
    for (int i=0; i<n; i++)
    {
        while (!dq.empty()&&i-dq.front().idx>k) dq.pop_front();
        while (!dq.empty()&&dq.back().h<=v[i]) dq.pop_back();
        //cout<<"front "<<dq.front().idx<<' '<<dq.front().mn<<'\n';
        //cout<<"back "<<dq.back().idx<<' '<<dq.back().mn<<'\n';
        while (!rl.empty()&&i-rl.front()>k) rl.pop_front();
        while (!rl.empty()&&v[rl.back()]<=v[i]) rl.pop_back();
        rl.push_back(i);
        if (!dq.empty())
        {
            auto tmp=dq.back();
            dq.pop_back();
            tmp.vl=tmp.idx>=0?dp[tmp.idx]+v[i]:v[i];
            //cout<<"tmp "<<tmp.h<<' '<<tmp.idx<<' '<<tmp.vl<<'\n';
            dq.push(tmp.h, tmp.idx, tmp.vl);
            dp[i]=dq.getmin();
        }
        else dp[i]=LLONG_MAX;
        //cout<<"bf "<<dp[i]<<'\n';
        dp[i]=min(dp[i], i<k?v[rl.front()]:dp[i-k]+v[rl.front()]);
        if (i<n-1) dq.push(v[i], i, dp[i]+v[i+1]);
        res=(res+p[n-i-1]*(dp[i]%mod))%mod;
        //cout<<"debug "<<i<<' '<<dp[i]<<'\n';
    }
    return res;
}

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