QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622081#6433. Klee in Solitary ConfinementYurily#WA 8ms58344kbC++141.7kb2024-10-08 19:47:442024-10-08 19:47:44

Judging History

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

  • [2024-10-08 19:47:44]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:58344kb
  • [2024-10-08 19:47:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int a[MAX],n,k;
vector<int> g[MAX];
priority_queue<pair<int,int> > q[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;
}
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);
		for(int j=0;j<g[i].size();++j){
			q[i].push(make_pair(j+1-findf(t,g[i][j]),j+1));
		}
	}
	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].top().second<l||q[x].top().first<=0))
			q[x].pop();
		if(!q[x].empty()){
			ans=max(ans,cnt0_l_1+q[x].top().first-cnt1_l_1+(int)g[xk].size());
		} 
		else{
			ans=max(ans,cnt0_l_1-cnt1_l_1+(int)g[xk].size());
		}
	}
	cout<<ans;
}// 9 -100 -1 -2 1 2 -1 -2 1 -2 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 58260kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 3ms
memory: 58320kb

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 7ms
memory: 58320kb

input:

7 1
2 3 2 3 2 3 3

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 7ms
memory: 58316kb

input:

9 -100
-1 -2 1 2 -1 -2 1 -2 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: 0
Accepted
time: 8ms
memory: 58324kb

input:

200 121649
0 527189 -1000000 -306471 -998939 527189 -1000000 -1000000 0 527189 0 527189 0 527189 -306471 -998939 -306471 -306471 -306471 0 0 527189 527189 1000000 527189 -1000000 1000000 648838 -1000000 -998939 -998939 -998939 0 1000000 -1000000 -998939 527189 1000000 648838 -1000000 1000000 648838 ...

output:

37

result:

ok 1 number(s): "37"

Test #6:

score: -100
Wrong Answer
time: 8ms
memory: 58344kb

input:

200 -454379
-385892 454379 -1000000 373644 -665078 -1000000 -1000000 454379 0 1000000 373644 -1000000 1000000 -385892 -1000000 373644 0 -665078 0 -665078 -1000000 -665078 -385892 -665078 -385892 454379 -665078 -385892 -1000000 454379 1000000 -385892 373644 454379 -1000000 -385892 -1000000 -385892 -1...

output:

48

result:

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