交互挂了,其他OJ可过
查看原帖
交互挂了,其他OJ可过
511676
naoliaok_lovely楼主2024/8/13 23:29

看了下报错,输出全是 11。

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, m, h[N], id[N];

int maxn[N][20];
void rmq()
{
	for(int i = 1; i <= n; i++)
	{
		maxn[i][0] = h[i];
		for(int j = 1; 1 << j <= i; j++)
			maxn[i][j] = max(maxn[i][j - 1], maxn[i - (1 << j - 1)][j - 1]);
	}
}

int getmax(int l, int r)
{
	int k = __lg(r - l + 1);
	return max(maxn[l + (1 << k) - 1][k], maxn[r][k]);
}

int l[N], r[N], q[N], tt, to[N][20], rr[N][20];
void init(int n, vector<int> H) 
{
	for(int i = 1; i <= n; i++) id[h[i] = H[i - 1]] = i;
	for(int i = 1; i <= n; i++)
	{
		while(tt && h[q[tt]] < h[i]) r[q[tt--]] = i;
		q[++tt] = i;
	}
	tt = 0;
	for(int i = n; i; i--)
	{
		while(tt && h[q[tt]] < h[i]) l[q[tt--]] = i;
		q[++tt] = i;
	}
	
	rmq();
	
	for(int i = n; i; i--)
	{
		int pos = id[i];
		if(l[pos] && r[pos]) to[pos][0] = h[l[pos]] > h[r[pos]] ? l[pos] : r[pos];
		else if(l[pos]) to[pos][0] = l[pos];
		else if(r[pos]) to[pos][0] = r[pos];
		for(int j = 1; j <= 18; j++)
			to[pos][j] = to[to[pos][j - 1]][j - 1];
	}
	for(int i = n; i; i--)
	{
		rr[i][0] = r[i];
		for(int j = 1; j <= 18; j++)
			rr[i][j] = rr[rr[i][j - 1]][j - 1];
	}
}

int minimum_jumps(int a, int b, int c, int d) 
{
	a++, b++, c++, d++;
	int maxn = getmax(c, d);
	if(getmax(b, c - 1) > maxn) return -1;
	
	int l1 = a, r1 = b;
	while(l1 < r1)
	{
		int mid = l1 + r1 >> 1;
		if(getmax(mid, c - 1) < maxn) r1 = mid;
		else l1 = mid + 1;
	}
	int now = id[getmax(l1, b)];
	l1 = c, r1 = d;
	while(l1 < r1)
	{
		int mid = l1 + r1 >> 1;
		if(getmax(c, mid) > getmax(now, c - 1)) r1 = mid;
		else l1 = mid + 1;
	}
	int minn = h[l1];
	
	int ans = 0;
	for(int i = 18; ~i; i--)
		if(to[now][i] && h[to[now][i]] < minn)
			ans += 1 << i, now = to[now][i];
	if(c <= r[now]) return ans + 1;
	if(l[now] && h[l[now]] < maxn) return ans + 2;
	for(int i = 18; ~i; i--)
		if(rr[now][i] && rr[now][i] < c)
			ans += 1 << i, now = rr[now][i];
	return ans + 1;
}
2024/8/13 23:29
加载中...