QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691117#5147. Stack Sorttsai#WA 0ms54588kbC++141.6kb2024-10-31 09:57:542024-10-31 09:57:55

Judging History

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

  • [2024-10-31 09:57:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:54588kb
  • [2024-10-31 09:57:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000050;
const int mod=1000000;


int a[N]={0};
int vis[2*mod+5000]={0};
vector<int>v[N];//下标
vector<int>num;
int lower(int need,int x){
	int ans=-1;
	int l=0,r=v[need].size()-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(v[need][mid]<x){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	return ans;
}
int upper(int need,int x){
	int ans=v[need].size();
	int l=0,r=v[need].size()-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(v[need][mid]>x){
			r=mid-1;
			ans=mid;
		}else{
			l=mid+1;
		}
	}
	return ans;
}
void solve(){
	int n,k;scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a[i]=x+mod;
		num.push_back(x+mod);//出现过那些数字
		v[x+mod].push_back(i);
	}
	int ans=0;
	for(auto x:num){
		ans=max(ans,(int)v[x].size());
	}
	if(k==0){
		cout<<ans;
		return;
	}
	for(auto x:num){
		if(vis[x]==1) continue;
		int need=x-k;
		vis[x]=1;
		for(int i=0;i<v[x].size();i++){
			if(need<0||need>2000005||v[need].size()==0)continue;
			int aa=lower(need,v[x][i]);//区间最右need
			int c1=lower(x,v[need][0]);
			int d1=upper(x,v[need][aa]);
			aa++;//前面有几个
			ans=max(ans,aa+(int)v[x].size()-(d1-c1-1));//改前面
			int bb=v[need].size()-aa;//后面有几个
			c1=lower(x,v[need][aa]);
			d1=upper(x,v[need][v[need].size()-1]);
			ans=max(ans,bb+(int)v[x].size()-(d1-c1-1));//改后面
		}
	}
	printf("%d",ans);
	return ;
}


int main(){
	int t=1;
//	scanf("%d",&t);
	while(t--){
		solve();
		if(t) printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 54588kb

input:

3
3
1 2 3
3
3 2 1
5
1 4 2 5 3

output:

1

result:

wrong answer 1st numbers differ - expected: '3', found: '1'