求助,本地测试样例可以输出 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;
}