QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#116862	#149. Peru	tricyzhkx^#	Compile Error	/	/	C++14	1.9kb	2023-06-30 09:30:49	2024-05-31 18:32:24

Judging History

你现在查看的是测评时间为 2024-05-31 18:32:24 的历史记录

[2024-09-10 16:35:00]
管理员手动重测本题所有提交记录

测评结果：100
用时：125ms
内存：132264kb

查看

[2024-05-31 18:32:24]
评测

测评结果：Compile Error
用时：0ms
内存：0kb

查看

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-30 09:30:49]
提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const ll INF=1e18;
ll f[2500010],minn[2500010];
int a[2500010],blo[2500010],L[2500010],R[2500010],stk[2500010],lc[2500010],rc[2500010],lim[2500010],pre[2500010],suf[2500010];
void upd(ll &a,ll b){a=min(a,b);}
pair<ll,ll> work(int u,ll mn)
{
	if(!u) return {INF,INF};
	auto p1=work(lc[u],mn);
	upd(f[u-1],min(mn,p1.second));upd(mn,min(p1.first,f[u-1])+a[u]);
	auto p2=work(rc[u],mn);
	ll ans1=min(min(p1.first,p2.first),f[u-1]),ans2=min(min(p1.first,f[u-1])+a[u],p2.second);
	return {ans1,ans2};
}
int solve(int n,int K,int *S)
{
	move(S,S+n,a+1);
	for(int i=0;i<=n;i++) blo[i]=i/K+1;
	for(int i=1;i<=blo[n];i++) L[i]=(i-1)*K,R[i]=min(i*K-1,n);
	for(int i=1;i<=blo[n];i++)
	{
		int l=L[i],r=R[i];
		pre[l]=a[l];suf[r]=a[r];
		for(int j=l+1;j<=r;j++) pre[j]=max(pre[j-1],a[j]);
		for(int j=r-1;j>=l;j--) suf[j]=max(suf[j+1],a[j]);
	}
	fill(f+1,f+n+1,INF);
	for(int i=1;i<=blo[n];i++)
	{
		if(i>1)
		{
			for(int j=L[i],k=R[i-1]-1;j<=R[i];j++)
			{
				for(;k>=L[i-1] && suf[k+1]<pre[j];k--);
				lim[j]=k;
			}
			ll mn=INF;
			minn[R[i-1]]=f[R[i-1]];
			for(int j=R[i-1]-1;j>=L[i-1];j--) minn[j]=min(minn[j+1],f[j]);
			for(int j=R[i];j>=L[i];j--)
			{
				if(lim[j]>=j-K)
				{
					if(j==R[i] || lim[j+1]<j+1-K)
						for(int k=j-K;k<=lim[j];k++)
							upd(mn,f[k]+suf[k+1]);
					else
					{
						upd(mn,f[j-K]+suf[j-K+1]);
						for(int k=lim[j+1]+1;k<=lim[j];k++) upd(mn,f[k]+suf[k+1]);
					}
					upd(f[j],mn);
				}
				upd(f[j],minn[max(lim[j]+1,j-K)]+pre[j]);
			}
		}
		int l=L[i],r=R[i],tp=0;
		for(int j=l+1;j<=r;j++)
		{
			while(tp && a[stk[tp]]<a[j]) lc[j]=stk[tp],tp--;
			if(tp) rc[stk[tp]]=j;
			stk[++tp]=j;
		}
		auto p=work(stk[1],INF);
		upd(f[r],p.second);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=(ans*23ll+f[i])%mod;
	return ans;
}

源文件, 语言: C++14

详细

implementer.cpp: In function ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~