Submission #850528

#	Time	Username	Problem	Language	Result	Execution time	Memory
850528		alexdd	Peru (RMI20_peru)	C++17	49 / 100	748 ms	72528 KiB

peru

#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;

set<pair<ll,int>> s;
void adauga(pair<ll,int> x)
{
    s.insert(x);
}
void sterge(pair<ll,int> x)
{
    s.erase(x);
}
pair<ll,int> getmin()
{
    auto it = s.begin();
    return *it;
}

ll dp[2500005];
int put23[2500005];
int a[2500005];
int solve(int n, int k, int* v)
{
    dp[0]=0;
    deque<pair<int,int>> dq;
    dq.push_back({0,0});
    a[0]=0;
    adauga({0,0});
    ll rez = 0;
    put23[0]=1;
    for(int i=1;i<=n;i++)
        put23[i]=(put23[i-1]*23LL)%MOD;
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
        if(!dq.empty() && i-dq.front().first>k)
        {
            pair<int,int> x = dq.front();
            sterge({dp[dq.front().first]+dq.front().second, dq.front().first});
            dq.pop_front();
            if(dq.empty() || dq.front().first > x.first+1)
            {
                dq.push_front({x.first+1,x.second});
                adauga({dp[x.first+1]+x.second, x.first+1});
            }
        }
        dp[i]=INF;
        int ult=-1;
        while(!dq.empty() && dq.back().second<a[i])
        {
            ult=dq.back().first;
            sterge({dp[dq.back().first]+dq.back().second, dq.back().first});
            dq.pop_back();
        }
        if(ult!=-1 && (dq.empty() || dq.back().second>a[i]))
        {
            dq.push_back({ult,a[i]});
            adauga({dp[ult]+a[i],ult});
        }

        /*cout<<i<<"\n";
        for(int j=0;j<dq.size();j++)
            cout<<dq[j].first<<" "<<dq[j].second<<"\n";
        cout<<"\n\n";*/
        dp[i] = getmin().first;
        dq.push_back({i,0});
        adauga({dp[i]+0,i});
        //cout<<i<<" "<<dp[i]<<" zzz\n";
        rez = (rez + ((dp[i]%MOD)*put23[n-i])%MOD)%MOD;
    }
    return rez;
}
/**

dp[i] = min(dp[j] + max(j+1..i))

*/

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