제출 #1291328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291328		HoriaHaivas	Peru (RMI20_peru)	C++20	0 / 100	1097 ms	50532 KiB

peru

#include<bits/stdc++.h>
#include "peru.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

int dp[2500005];
signed S[2500005];
int v[2500005];
int dir[2500005];
deque<pair<int,int>> deqe;
const int mod=1e9+7;
const int inf=1e18;

class coada
{
public:
    pair<int,int> fr[2500005];
    int mif[2500005]={inf};
    pair<int,int> bk[2500005];
    int mib[2500005]={inf};
    int tfr=0;///scuze
    int tbk=0;///scuze

    void push(int idxdp, int idxmx)
    {
        tbk++;
        bk[tbk]= {idxdp,idxmx};
        mib[tbk]=min(mib[tbk-1],dp[idxdp]+v[idxmx]);
    }

    void pop()
    {
        if (tfr==0)
        {
            while (tbk>0)
            {
                tfr++;
                fr[tfr]=bk[tbk];
                mif[tfr]=min(mif[tfr-1],dp[bk[tbk].first]+v[bk[tbk].second]);
                tbk--;
            }
        }
        if (fr[tfr].first<fr[tfr].second-1)
        {
            fr[tfr].first++;
            mif[tfr]=min(mif[tfr-1],dp[fr[tfr].first]+v[fr[tfr].second]);
        }
        else
        {
            tfr--;
        }
        if (tfr<0 || tbk<0)
        {
            while (true)
            {

            }
        }
    }

    bool empti()
    {
        if (tfr+tbk==0)
            return 1;
        else
            return 0;
    }

    pair<int,int> froont()
    {
        if (tfr!=0)
        return fr[tfr];
        else
        return bk[1];
    }

    pair<int,int> bek()
    {
        if (tbk!=0)
        return bk[tbk];
        else
        return fr[1];
    }

    int query_min()
    {
        int ans;
        ans=min(mif[tfr],mib[tbk]);
        return ans;
    }
};

class dqSigma
{
public:
    coada q;
    pair<int,int> st[2500005];
    int mi[2500005]={inf};
    int t=0;///scuze din nou

    void pop_bk()
    {
        t--;
    }

    void pop_fr()
    {
        q.pop();
    }

    void push_bk(int idxdp, int idxmx)
    {
        if (dir[idxmx]==1)
        {
            t++;
            st[t]= {idxdp,idxmx};
            mi[t]=min(mi[t-1],dp[idxdp]+v[idxmx]);
        }
        else
        {
            q.push(idxdp,idxmx);
        }
    }

    bool empti()
    {
        if (q.empti() && t==0)
            return 1;
        else
            return 0;
    }

    pair<int,int> fr()
    {
        if (!q.empti())
        return q.froont();
        else
        return st[1];
    }

    pair<int,int> bk()
    {
        if (t!=0)
        return st[t];
        else
        return q.bek();
    }

    int query_min()
    {
        int ans;
        ans=min(q.query_min(),mi[t]);
        return ans;
    }
} dq;

int lgpow(int x, int p)
{
    int ans,pw,i;
    ans=1;
    pw=x;
    for (i=0; i<30; i++)
    {
        if (p&(1<<i))
            ans=(ans*pw)%mod;
        pw=(pw*pw)%mod;
    }
    return ans;
}

signed solve(signed N, signed K, signed* S)
{
    int n,k,i,j,ans,imin;
    n=N;
    k=K;
    for (i=1; i<=n; i++)
    {
        v[i]=S[i-1];
    }
    deqe.push_back({0,0});
    for (i=1; i<=n; i++)
    {
        if (i!=1)
        {
            while (!deqe.empty() && deqe.front().first<i-k)
            {
                deqe.front().first++;
            }
            if (!deqe.empty() && deqe.front().first>=deqe.front().second)
            {
                dir[deqe.front().second]=0;
                deqe.pop_front();
            }
            if (!deqe.empty())
                assert(deqe.front().first>=i-k);
        }
        imin=i-1;
        while (!deqe.empty() && v[deqe.back().second]<v[i])
        {
            imin=min(imin,deqe.back().first);
            dir[deqe.back().second]=1;
            deqe.pop_back();
        }
        deqe.push_back({imin,i});
    }
    deqe.clear();
    dq.push_bk(0,0);
    ans=0;
    for (i=1; i<=n; i++)
    {
        if (i!=1)
        {
            while (!dq.empti() && dq.fr().first<i-k)
            {
                dq.pop_fr();///asta defapt imi incrementeaza first si in cazul in care nu e bine ii si da pop
            }
            if (!dq.empti())
                assert(dq.fr().first>=i-k);
        }
        imin=i-1;
        while (!dq.empti() && v[dq.bk().second]<v[i])
        {
            imin=min(imin,dq.bk().first);
            dq.pop_bk();
        }
        dq.push_bk(imin,i);
        dp[i]=dq.query_min();
        ans+=((dp[i]%mod)*lgpow(23,n-i))%mod;
        ans%=mod;
    }
    return ans;
}

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