QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#622176#6433. Klee in Solitary ConfinementYurily#ML 0ms0kbC++201.9kb2024-10-08 20:07:152024-10-08 20:07:16

Judging History

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

  • [2024-10-08 20:07:16]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-08 20:07:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int a[MAX],n,k;
vector<int> g[MAX];
struct node{
	int v,id;
};
queue<node> q[MAX];
node tmp[MAX];
set<int> s;
int d[MAX],tot;
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;
}

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 findx(int x){
	int l=1,r=tot;
	while(l<=r){
		int mid=l+r>>1;
		if(d[mid]==x){
			return mid;
		}
		else{
			if(d[mid]>x)
				r=mid-1;
			else
				l=mid+1; 
		}
	}
	return -1;
}
bool cmp(node x,node y){
	return x.v>y.v;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		a[i]=read();
		s.insert(a[i]);
	}
	for(set<int>::iterator i=s.begin();i!=s.end();++i){
		d[++tot]=*i;
	}
	for(int i=1;i<=n;++i){
		g[findx(a[i])].push_back(i);
	}
	int ans=0;
	for(int i=1;i<=tot;++i){
		ans=max(ans,(int)g[i].size());
		if(!g[i].size()||findx(d[i]+k)==-1)
			continue;
		int t=findx(d[i]+k);
		int cur=0;
		for(auto j=g[i].begin();j!=g[i].end();++j){
		//	q[i].push(make_pair(cur-findf(t,*j),cur));
			cur++;
			tmp[cur].id=cur;
			tmp[cur].v=cur-findf(t,*j);
		}
		sort(tmp+1,tmp+1+cur,cmp);
		for(int j=1;j<=cur;++j)
			q[i].push(tmp[i]);
	}
	for(int i=1;i<=n;++i){
		int x=findx(a[i]),xk=findx(a[i]+k);
		if(xk==-1)
			continue;
		int l=findf(x,i);
	
		int cnt0_l_1=findf(xk,i-1);	
		int cnt1_l_1=findf(x,i-1);
		while(!q[x].empty()&&q[x].front().id<l)
			q[x].pop();
		if(!q[x].empty()){
			ans=max(ans,cnt0_l_1+q[x].front().v-cnt1_l_1+(int)g[xk].size());
		} 
	}
	cout<<ans;
}// 9 -100 -1 -2 1 2 -1 -2 1 -2 1

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

5 2
2 2 4 4 4

output:

5

result: