我裂开了 -- 本地 AC 线上全 WA
查看原帖
我裂开了 -- 本地 AC 线上全 WA
119491
5ab_juruo楼主2020/10/1 09:50

求助,本地测试样例可以输出 5,但 OJ 上就输出 6 了。

提交记录:https://www.luogu.com.cn/record/39073063

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

constexpr int max_n = 100000, max_sq = 4;
int a[max_n], pl[max_n][max_sq*2+1], cnt[max_n], dp[max_n+1] = {-1}, ans = 0;

inline bool icmp(int a, int b) { return a > b; }

#define gc getchar
inline int read()
{
	int c = gc(), t = 1, n = 0;
	while (isspace(c)) { c = gc(); }
	if (c == '-') { t = -1, c = gc(); }
	while (isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
	return n * t;
}
#undef gc

int ser(int nk)
{
	int lb = 0, ub = ans + 1, mid, ret = 0;

	while (lb < ub)
	{
		mid = (lb + ub) >> 1;

		if (dp[mid] < nk)
			ret = mid, lb = mid + 1;
		else
			ub = mid;
	}

	return ret + 1;
}

int main()
{
	memset(a, -1, sizeof(a));

	int n = read(), tmp;

	for (int i = 0; i < n; i++)
	{
		tmp = read() - 1;
		a[tmp] = i;
	}

	for (int i = 0, k; i < n; i++, k = 0)
	{
		tmp = read() - 1;

		for (int j = tmp; j >= 0 && k <= max_sq; j--, k++)
			pl[i][k] = a[j];
		for (int j = tmp + 1, t = 0; j < n && t <= max_sq; j++, k++, t++)
			pl[i][k] = a[j];
		
		cnt[i] = k;
		sort(pl[i], pl[i] + k, icmp);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < cnt[i]; j++)
		{
		//	printf("%d ", pl[i][j]);
			tmp = ser(pl[i][j]);
			dp[tmp] = pl[i][j];

			if (tmp > ans)
				ans = tmp;
		}
	//	putchar('\n');
	}
	
	printf("%d\n", ans);

	return 0;
}
2020/10/1 09:50
加载中...