记录编号	576967	评测结果	AAAATTTTTT
题目名称	坐标压缩	最终得分	40
用户昵称	op_组撒头屯	是否通过	未通过
代码语言	C++	运行时间	12.004 s
提交时间	2022-10-19 19:07:23	内存使用	12.37 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+5;
int n,cnt;ll s;
int a[N],b[N],c[N];
vector<int>v[N];
inline int read(){
	int tmp=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))tmp=(tmp<<3)+(tmp<<1)+(ch^48),ch=getchar();
	return tmp;
}
struct sdf{
	int l,r,mx;
}tr[4*N];
void pushup(int pt){
	tr[pt].mx=max(tr[pt*2].mx,tr[pt*2+1].mx);
	return ;
}
void build(int pt,int l,int r){
	tr[pt]={l,r,0};
	if (l==r)return ;
	int mid=(l+r)/2;
	build(pt*2,l,mid);build(pt*2+1,mid+1,r);
	return ;
}
void change(int pt,int pos,int x){
	int l=tr[pt].l,r=tr[pt].r;
	if (l==r){
		tr[pt].mx=x;return ;
	}
	int mid=(l+r)/2;
	if (pos<=mid)change(pt*2,pos,x);
	else change(pt*2+1,pos,x);
	pushup(pt);
	return ;
}
int query(int pt,int x,int y){
	int l=tr[pt].l,r=tr[pt].r;
	if (x<=l&&r<=y)return tr[pt].mx;
	int mid=(l+r)/2,tmp=0;
	if (x<=mid)tmp=max(tmp,query(pt*2,x,y));
	if (mid+1<=y)tmp=max(tmp,query(pt*2+1,x,y));
	return tmp;
}
bool check(int k){
	build(1,1,n);
	ll tot=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<v[i].size();j++){
			int p=v[i][j],l=max(1,p-k),r=min(n,p+k);
			c[p]=query(1,l,r)+1;
			tot+=c[p];
		}
		for (int j=0;j<v[i].size();j++)change(1,v[i][j],c[v[i][j]]);
	}
	return tot<=s;
}
int main(){
	freopen ("coord.in","r",stdin);
	freopen ("coord.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%lld",&n,&s);
		for (int i=1;i<=n;i++){
			a[i]=read(),b[i]=a[i];
			v[i].clear();
		}
		sort(b+1,b+n+1);
		cnt=unique(b+1,b+n+1)-b-1;
		ll t=0;
		for (int i=1;i<=n;i++){
			a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
			t+=a[i];v[a[i]].push_back(i);
		}
		if (t<=s){
			printf("%d\n",n+1);continue;
		}
		int l=1,r=n;
		while(l<r){
			int mid=(l+r+1)/2;
			if (check(mid))l=mid;
			else r=mid-1;
		}
		printf("%d\n",l+1);
	}
	return 0;
}