QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311340#7904. Rainbow SubarrayconfesserTL 1ms9716kbC++171.6kb2024-01-22 11:04:332024-01-22 11:04:34

Judging History

你现在查看的是最新测评结果

  • [2024-06-09 00:00:26]
  • hack成功,自动添加数据
  • (/hack/652)
  • [2024-01-22 11:04:34]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9716kb
  • [2024-01-22 11:04:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using pi=pair<int,int>;
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define G(i,a,b) for(int i=(a);i>=(b);i--)
#define ms(a,b) memset(a,b,sizeof(a))
#define si(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define fi first
#define se second
#define pb push_back

const int N=5e5+3;
int n,a[N],b[N],m,rk[N];

struct bit{
	int n;
	ll c[N];
	void init(int m){
		n=m;
		F(i,1,n) c[i]=0;
	}
	void add(int i,ll k){
		for(;i<=n;i+=i&-i) c[i]+=k; 
	}
	ll qry(int i){
		int res=0;
		for(;i>=1;i-=i&-i) res+=c[i];
		return res;
	}
	ll qry(int l,int r){
		if(l>r) return 0;
		return qry(r)-qry(l-1);
	}
}c1,c2;

void add(int x){
	c1.add(rk[x],1);
	c2.add(rk[x],a[x]);
}
void del(int x){
	c1.add(rk[x],-1);
	c2.add(rk[x],-a[x]);
}
int get(){
	int n=c1.qry(m),l=1,r=m,res=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(c1.qry(mid-1)<=n/2){
			res=mid;
			l=mid+1;
		}else r=mid-1;
	}
	return b[res];
}
ll val(){
	int x=get(),y=upper_bound(b+1,b+m+1,x)-b-1;
	return (ll)c1.qry(y)*x-c2.qry(y)+c2.qry(y+1,m)-(ll)c1.qry(y+1,m)*x;
}

void slv(){
	ll k;
	cin>>n>>k;
	F(i,1,n){
		cin>>a[i];
		a[i]-=i;
		b[++m]=a[i];
	}
	sort(b+1,b+m+1);
	m=unique(b+1,b+m+1)-b-1;
	F(i,1,n) rk[i]=lower_bound(b+1,b+m+1,a[i])-b;
	c1.init(m);
	c2.init(m);
	int j=1,ans=0;
	F(i,1,n){
		add(i);
		while(j<i&&val()>k) del(j++);
		ans=max(ans,i-j+1);
	}
	cout<<ans<<'\n';
}

int main(){
	cin.tie(0)->ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) slv();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 9716kb

input:

5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3

output:

4
3
5
1
1

result:

ok 5 lines

Test #2:

score: -100
Time Limit Exceeded

input:

11102
2 167959139
336470888 134074578
5 642802746
273386884 79721198 396628655 3722503 471207868
6 202647942
268792718 46761498 443917727 16843338 125908043 191952768
2 717268783
150414369 193319712
6 519096230
356168102 262263554 174936674 407246545 274667941 279198849
9 527268921
421436316 3613460...

output:

1
4
3
2
6
5
7
2
4
1
4
1
1
3
2
2
7
9
7
10
1
7
6
2
4
3
1
7
7
7
3
4
3
10
3
8
6
6
3
1
6
3
1
2
4
6
4
7
4
1
4
7
1
6
3
5
6
6
1
7
5
3
1
6
4
5
3
2
2
6
2
3
10
1
4
3
2
4
5
1
7
5
5
5
8
5
3
6
3
5
5
9
5
4
5
2
1
5
2
3
3
4
8
1
3
1
2
2
8
3
1
6
8
1
8
4
5
6
6
10
4
8
3
2
8
4
5
6
2
6
2
4
1
5
4
5
3
2
4
1
2
1
4
5
8
3
7
3
...

result: