QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621993#6433. Klee in Solitary ConfinementYurily#ML 0ms0kbC++141.8kb2024-10-08 19:14:352024-10-08 19:14:36

Judging History

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

  • [2024-10-08 19:14:36]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-08 19:14:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6;
int a[MAX+5],n,k;
vector<int> g[MAX*2+5];
struct node{
	int v,id;
};
queue<node> q[MAX*2+5];
node tmp[MAX+5];
int findf(int u,int x){
	int l=0,r=(int)g[u].size()-1,res=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(g[u][mid]<=x){
			res=mid;
			l=mid+1;
		}
		else
			r=mid-1;
	}
	return res+1;
}
bool cmp(node x,node y){
	return x.v>y.v||x.v==y.v&&x.id<y.id;
}

int read(){
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){
		if(c == '-'){
			f = -1;
		}
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x*10+c-'0';
		c = getchar();
	}
	return x*f;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		a[i]=read();
		g[a[i]+MAX].push_back(i); 
	}
	
	int ans=0;
	for(int i=0;i<=MAX*2;++i){
		ans=max(ans,(int)g[i].size());
		if(!g[i].size()||i+k>MAX*2||i+k<0)
			continue;
		for(int j=0;j<g[i].size();++j){
			tmp[j+1].id=j+1;
			tmp[j+1].v=j+1-findf(i+k,g[i][j]);
		}
		sort(tmp+1,tmp+1+g[i].size(),cmp);
		for(int j=1;j<=(int)g[i].size();++j){
			if(tmp[j].v<=0)
				break;
			q[i].push(tmp[j]);
		}
//		cout<<i-MAX<<"  ";
//		for(int j=1;j<=(int)g[i].size();++j){
//			cout<<tmp[j].id<<" "<<tmp[j].v<<"  ";
//		}			
//		cout<<endl;
	}
//	cout<<ans<<endl;
	for(int i=1;i<=n;++i){
		if(a[i]+k>MAX||a[i]+k<-MAX)
			continue;
		int l=findf(a[i]+MAX,i);
	
		int cnt0_l_1=findf(a[i]+k+MAX,i-1);	
		int cnt1_l_1=findf(a[i]+MAX,i-1);
//		cout<<i<<" "<<l<<" "<<cnt0_l_1<<endl;
		while(!q[a[i]+MAX].empty()&&q[a[i]+MAX].front().id<l)
			q[a[i]+MAX].pop();
		if(!q[a[i]+MAX].empty()){
			ans=max(ans,cnt0_l_1+q[a[i]+MAX].front().v-cnt1_l_1+(int)g[a[i]+k+MAX].size());
		} 
		else{
			ans=max(ans,cnt0_l_1-cnt1_l_1+(int)g[a[i]+k+MAX].size());
		}
	}
	cout<<ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Memory Limit Exceeded

input:

5 2
2 2 4 4 4

output:

5

result: