记录编号	576899	评测结果	AAAAAAAAAA
题目名称	坐标压缩	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	15.142 s
提交时间	2022-10-18 09:11:46	内存使用	9.63 MiB

#include <bits/stdc++.h>
#define pb emplace_back

int read() {
	int s = 0;
	char c = getchar();
	for(;c < '0'||c > '9';c = getchar());
	for(;c >= '0'&&c <= '9';c = getchar())
		s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}

int max(int x,int y) {
	return x > y ? x : y;
}

int min(int x,int y) {
	return x > y ? y : x;
}

const int maxn = 1e5 + 5;
int n,a[maxn],s,c[maxn],cnt,pos[maxn];
std::list<int> G[maxn];

int sum[maxn << 2],M;

void build() {
	for(M = 1;M <= n + 1;M <<= 1);
	for(int i = 1;i <= n + M;++ i)sum[i] = 0;
	return ;
}

void modify(int pos,int val) {
	sum[pos += M] = val;
	for(pos >>= 1;pos;pos >>= 1)
		sum[pos] = max(sum[pos << 1] , sum[pos << 1 | 1]);
	return ;
}

int query(int l,int r) {
	l = l + M - 1;
	r = r + M + 1;
	int res = 0;
	while(l ^ r ^ 1) {
		if(~ l & 1)res = max(res , sum[l ^ 1]);
		if(r & 1)res = max(res , sum[r ^ 1]);
		l >>= 1;
		r >>= 1;
	}
	return res;
}

bool check(int k) {
	int ans = 0;
	build();
	for(int i = 1;i <= cnt;++ i) {
		for(auto& v : G[i]) {
			int l = max(v - k , 1),r = min(v + k , n);
			pos[v] = query(l , r) + 1;
			ans += pos[v];
			if(ans > s)return false;
		}
		for(auto& v : G[i]) {
			modify(v , pos[v]);
		}
	}
	return ans <= s;
}

void work() {
	n = read();
	s = read();
	cnt = 0;
	for(int i = 1;i <= n;++ i)
		c[++ cnt] = a[i] = read();
	std::sort(c + 1 , c + 1 + cnt);
	cnt = std::unique(c + 1 , c + 1 + cnt) - c - 1;
	for(int i = 1;i <= n;++ i)
		a[i] = std::lower_bound(c + 1 , c + 1 + cnt , a[i]) - c;
	for(int i = 1;i <= cnt;++ i)
		G[i].clear();
	for(int i = 1;i <= n;++ i)
		G[a[i]].pb(i);
	
	int l = 0,r = n;
	while(l <= r) {
		int mid = l + r >> 1;
		if(check(mid))l = mid + 1;
		else r = mid - 1;
	}
	
	printf("%d\n",r + 1);
	return ;
}

int main() {
	freopen("coord.in","r",stdin);
	freopen("coord.out","w",stdout);
	int T = read();
	while(T --)work();
	return 0;
}