QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277088#7904. Rainbow Subarraymiku_HYTL 1051ms11440kbC++203.9kb2023-12-06 15:16:442023-12-06 15:16:46

Judging History

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

  • [2024-06-09 00:00:26]
  • hack成功,自动添加数据
  • (/hack/652)
  • [2023-12-06 15:16:46]
  • 评测
  • 测评结果:TL
  • 用时:1051ms
  • 内存:11440kb
  • [2023-12-06 15:16:44]
  • 提交

answer

/*[[
 ⣇⣿⠘⣿⣿⣿⡿⡿⣟⣟⢟⢟⢝⠵⡝⣿⡿⢂⣼⣿⣷⣌⠩⡫⡻⣝⠹⢿⣿⣷ ]],[[
 ⡆⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑⢝⣇ ]],[[
 ⡆⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐⢕⢽ ]],[[
 ⡗⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐⣕⢕ ]],[[
 ⡝⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀⢱⢕ ]],[[
 ⡝⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇⡀⢕ ]],[[
 ⡝⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰⢗⢄ ]],[[
 ⠁⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕⢕⢕ ]],[[
 ⡀⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵⣵⣿ ]],[[
 ⡻⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ]],[[
 ⣷⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟ ]],[[
 ⡕⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿⠁⣠ ]],[[
 ⡝⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀⣈⠙ ]],[[
 ⡝⡵⡕⡀⠑⠳⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⡠⡲⡫⡪⡪⡣ ]],*/
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define int long long
using namespace std;
using ll =long long ;
using pii =pair<int,int>;
using pll=pair<ll,ll>;
using pcc=pair<char,char>;
bool cmp(pll a,pll b){
	return a.y<b.y;
}
struct cmp1{
    bool operator()(pair<ll,ll>a,pair<ll,ll>b){
	if(a.x==b.x)return a.y>b.y;
	return a.x>b.x; 
}
};
const int mod=998244353;
ll ksm(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1){
			ans*=a;
		ans=ans%mod;
		}
		a=a*a;a%=mod;
		b>>=1;
	}
	return ans;
}
ll gcd(ll a,ll b){
	ll t=a%b;
	while(t){
		a=b;
		b=t;
		t=a%b;
	}
	return b;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
ll get_inv(ll x){
	return ksm(x,mod-2);
}
const int N=1e6+10;
ll n,k;
ll a[N];
/* 
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
*/
bool check(ll x){
	if(x==1)return true;
	unordered_map<ll,int>mp;
//	cout<<x<<endl;
	ll ans=1e18;
	set<int>zh,fu;
	ll res=0;
	int lenzh=0,lenfu=0;
	ll base=0,basex=0;ll tt=0;
	for(int i=1;i<=n;++i){
		ll w=a[i]-i;
		if(w==base)++basex;
		++mp[w];
		if(w<base){
			++lenfu;
			if(mp[w]==1)fu.insert(w);
		}
		if(w>base){
			++lenzh;
			if(mp[w]==1)zh.insert(w);
		}
		res+=abs(w-base);
		if(i>x){
			ll tw=a[i-x]-(i-x);
			--mp[tw];
			res-=abs(tw-base);
			if(tw>base){
				lenzh--;
				if(mp[tw]==0){
				auto t=zh.find(tw);
				zh.erase(t);
				}
			}
			if(tw<base){
				lenfu--;
				if(mp[tw]==0){
				auto t=fu.find(tw);
				fu.erase(t);
				}
			}
			if(tw==base)basex--;
		}
		
		while(lenzh>basex+lenfu){
			if(zh.size()==0)break;
			auto t=zh.begin();
			ll w=abs(*t-base);
			res-=w*abs(basex+lenfu-lenzh);
		//	cout<<w*abs(basex+lenfu-lenzh)<<endl;
			fu.insert(base);w=*t;
			lenfu+=basex;
			basex=mp[w];
			base=w;
			lenzh-=mp[w];
			zh.erase(t);
		}
		while(lenfu>basex+lenzh){
			if(fu.size()==0)break;
			auto t=--fu.end();
			ll w=abs((*t)-base);
			res-=w*abs(basex+lenzh-lenfu);
			zh.insert(base);
			w=*--fu.end();
			lenzh+=basex;
			basex=mp[w];
			base=w;
			lenfu-=mp[w];
			fu.erase(t);
		}
		if(i>=x)ans=min(ans,res);
	if(ans<=k)return true;
	}
	
	return false;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	ll l=1,r=n;
	ll tt=0;
	while(l<r){
		ll mid=(l+r+1)>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cout.tie(0);
	int _=1;
	cin>>_;
	while(_--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0
Accepted
time: 1051ms
memory: 11440kb

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
8
7
7
1
7
6
2
4
3
1
6
7
7
3
4
3
9
3
8
6
6
3
1
6
3
1
2
4
6
4
6
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
8
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
8
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
3
3...

result:

ok 11102 lines

Test #3:

score: -100
Time Limit Exceeded

input:

1
500000 17244641009859
54748096 75475634 204928248 276927808 84875072 103158867 27937890 322595515 186026685 45468307 69240390 139887597 188586447 373764525 121365644 310156469 185188306 60350786 211308832 384695957 370562147 208427221 35937909 267590963 126478310 275357775 55361535 335993561 36696...

output:


result: