oj.uz

Submission #401541

# Submission time Handle Problem Language Result Execution time Memory
401541 2021-05-10T13:18:29 Z Pyqe Peru (RMI20_peru) C++14
0 / 100
 32 ms 59220 KB 
#include <bits/stdc++.h>
#include "peru.h"

using namespace std;

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

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

void bd(long long x)
{
	long long 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(long long x,long long cw)
{
	long long i,sz=al[x].size(),l;
	
	dp[x]=min(cw,dp[max(x-d,0ll)]+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)
{
	long long 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--);
		al[sk[nn]].push_back(i);
		nn++;
		sk[nn]=i;
		for(j=min(j,nn);sk[j]<=max(i-d,0ll);j++);
		sr[i]=sk[j];
	}
	bd(0);
	dfs(0,inf);
	for(i=n;i;i--)
	{
		z=(z+dp[i]*ml)%dv;
		ml=ml*m%dv;
	}
	return z;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 59220 KB Output is correct
2 Incorrect 32 ms 59212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 59220 KB Output is correct
2 Incorrect 32 ms 59212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 59220 KB Output is correct
2 Incorrect 32 ms 59212 KB Output isn't correct
3 Halted 0 ms 0 KB -