QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#116818	#149. Peru	He_Ren^#	Compile Error	/	/	C++17	1.9kb	2023-06-30 08:51:13	2024-05-31 18:30:12

Judging History

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

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

测评结果：0
用时：3ms
内存：16044kb

查看

[2024-05-31 18:30:12]
评测

测评结果：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 08:51:13]
提交

answer

#include<bits/stdc++.h>
#include"peru.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2.5e5 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;

int n,d;
int a[MAXN];

ll f[MAXN];

void divid(int l,int mid,int r)
{
	static int premx[MAXN], sufmx[MAXN];
	
	premx[mid] = -inf;
	for(int i=mid+1; i<=r; ++i)
		premx[i] = max(premx[i-1], a[i]);
	
	sufmx[mid+1] = -inf;
	for(int i=mid; i>=l; --i)
		sufmx[i] = max(sufmx[i+1], a[i]);
	
	static ll mn[MAXN];
	mn[mid+1] = linf;
	for(int i=mid; i>=l; --i)
		mn[i] = min(mn[i+1], f[i]);
	
	for(int i=mid+1,j=mid; i<=r; ++i)
	{
		while(j>=l && sufmx[j] <= premx[i]) --j;
		int pos = max(i-d, j);
		f[i] = min(f[i], mn[pos] + premx[i]);
	}
	
	static ll tag[MAXN];
	for(int i=mid; i<=r+1; ++i)
		tag[i] = linf;
	
	for(int i=mid,j=mid+1; i>=l; --i)
	{
		while(j<=r && premx[j] <= sufmx[i+1]) ++j;
		int pos = min(i+d, j-1);
		tag[pos] = min(tag[pos], f[i] + sufmx[i+1]);
	}
	
	for(int i=r; i>=mid+1; --i)
	{
		tag[i] = min(tag[i], tag[i+1]);
		f[i] = min(f[i], tag[i]);
	}
}

int solve(int _n, int _d, int *_a)
{
	n = _n; d = _d;
	for(int i=1; i<=n; ++i)
		a[i] = _a[i-1];
	
	fill(f+1, f+n+1, linf);
	f[0] = 0;
	
	for(int l=0,r; l<=n; l=r+1)
	{
		r = min(l+d-1, n);
		
		static pair<ll,int> sta[MAXN];
		int tp = 0;
		for(int i=l; i<=r; ++i)
		{
			ll cur = f[i];
			while(tp && sta[tp].second <= a[i])
				cur = min(cur, sta[tp].first), --tp;
			
			if(tp == 0 || cur + a[i] < sta[tp].first + sta[tp].second)
				sta[++tp] = {cur, a[i]};
			
			if(tp) f[i] = min(f[i], sta[tp].first + sta[tp].second);
		}
		
		if(r < n)
			divid(l, r, min(r+d, n));
	}
	
	int ans = 0, curpw = 1;
	for(int i=n; i>=1; --i)
	{
		ans = (ans + (ll)f[i] %mod * curpw) %mod;
		curpw = (ll)curpw * 23 %mod;
	}
	return ans;
}

源文件, 语言: C++17

详细

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;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~