Submission #401542

#	Time	Username	Problem	Language	Result	Execution time	Memory
401542		Pyqe	Peru (RMI20_peru)	C++14	49 / 100	303 ms	262144 KiB

peru

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

using namespace std;

const long long m=23,dv=1e9+7,inf=1e18;
long long nn=0,a[2500069],dp[2500069],sk[2500069];

struct segtree
{
	long long l,r,mn,lz;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		mn=0;
		lz=0;
		if(l<r)
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void blc()
	{
		long long ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mn+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(long long lh,long long rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn+=w;
			lz+=w;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh,w);
			}
			mn=min(p[0]->mn,p[1]->mn);
		}
	}
	long long qr(long long lh,long long rh)
	{
		if(l>rh||r<lh)
		{
			return inf;
		}
		else if(l>=lh&&r<=rh)
		{
			return mn;
		}
		else
		{
			blc();
			return min(p[0]->qr(lh,rh),p[1]->qr(lh,rh));
		}
	}
}
sg;

int solve(int n,int d,int* aa)
{
	long long i,ml=1,z=0;
	
	sg.bd(1,n);
	for(i=1;i<=n;i++)
	{
		a[i]=aa[i-1];
		for(;nn&&a[sk[nn]]<=a[i];nn--)
		{
			sg.ud(sk[nn-1]+1,sk[nn],a[i]-a[sk[nn]]);
		}
		nn++;
		sk[nn]=i;
		sg.ud(i,i,dp[i-1]+a[i]);
		dp[i]=sg.qr(max(i-d+1,1ll),i);
	}
	for(i=n;i;i--)
	{
		z=(z+dp[i]%dv*ml)%dv;
		ml=ml*m%dv;
	}
	return z;
}

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