제출 #401551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401551		Pyqe	Peru (RMI20_peru)	C++14	18 / 100	74 ms	80008 KiB

peru

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

using namespace std;

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

struct segtree
{
	int l,r;
	long long mn,lz;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		mn=0;
		lz=0;
		if(l<r)
		{
			int 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()
	{
		int ii;
		
		for(ii=0;ii<2;ii++)
		{
			p[ii]->mn+=lz;
			p[ii]->lz+=lz;
		}
		lz=0;
	}
	void ud(int lh,int rh,long long w)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			mn+=w;
			lz+=w;
		}
		else
		{
			int 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(int lh,int 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)
{
	int 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,1),i);
	}
	for(i=n;i;i--)
	{
		z=(dp[i]%dv*ml+z)%dv;
		ml=(long long)ml*m%dv;
	}
	return z;
}

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