Submission #401636

#	Time	Username	Problem	Language	Result	Execution time	Memory
401636		Pyqe	Peru (RMI20_peru)	C++14	100 / 100	343 ms	229332 KiB

peru

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

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const int m=23,dv=1e9+7;
const long long inf=1e18;
int d,nn=0,a[2500069],sk[2500069],fh[2500069],sr[2500069];
long long dp[2500069];
vector<int> al[2500069];
deque<pair<int,long long>> dq;
bitset<2500069> spc;

void bd(int x)
{
	int i,sz=al[x].size(),l;
	
	fh[x]=x;
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		bd(l);
		fh[x]=max(fh[x],fh[l]);
	}
}

void dfs(int x,long long cw)
{
	int i,sz=al[x].size(),l;
	
	dp[x]=min(cw,dp[max(x-d,0)]+a[sr[x]]);
	for(;!dq.empty()&&dq.front().fr<x-d;dq.pop_front());
	if(!dq.empty())
	{
		dp[x]=min(dp[x],dq.front().sc);
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(fh[l]-d>x)
		{
			for(;!dq.empty()&&dq.back().sc>=dp[x]+a[l];dq.pop_back());
			dq.push_back({x,dp[x]+a[l]});
			dfs(l,cw);
		}
		else
		{
			dfs(l,min(cw,dp[x]+a[l]));
		}
	}
}

int solve(int n,int od,int* aa)
{
	int i,j,ml=1,z=0;
	
	d=od;
	for(j=0,i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		for(;nn&&a[sk[nn]]<=a[i];nn--)
		{
			spc[sk[nn]]=0;
		}
		al[sk[nn]].push_back(i);
		nn++;
		sk[nn]=i;
		spc[i]=1;
		for(;j<=i-d||!spc[j];j++);
		sr[i]=j;
	}
	bd(0);
	dfs(0,inf);
	for(i=n;i;i--)
	{
		z=(z+dp[i]%dv*ml)%dv;
		ml=(long long)ml*m%dv;
	}
	return z;
}

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