QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694116#6433. Klee in Solitary Confinements2328995024sWA 158ms224712kbC++141.6kb2024-10-31 17:17:302024-10-31 17:17:32

Judging History

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

  • [2024-10-31 17:17:32]
  • 评测
  • 测评结果:WA
  • 用时:158ms
  • 内存:224712kb
  • [2024-10-31 17:17:30]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1e6;
int n,k,lst[2000005],a[2000005];
vector<int> oc[2000005];
vector<int> st[2000005];
int main()
{
//	oc[0].push_back(0);oc[0].push_back(1);oc[0].push_back(2);
//	int tt = upper_bound(oc[0].begin(),oc[0].end(),1)-oc[0].begin();
//	cout<<tt<<endl;
	cin>>n>>k;
	for(int i=0;i<=N*2;++i) st[i].push_back(0),oc[i].push_back(0);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		oc[a[i]+N].push_back(i);
		if(a[i]-k<-N||a[i]-k>N) continue;
		int temp=st[a[i]+N].size();
		if(lst[a[i]+N]<lst[N+a[i]-k])
		{
			st[a[i]+N].push_back(st[a[i]+N][temp-1]);
		}
		else st[a[i]+N].push_back(temp);
		lst[a[i]+N]=i;
	}
	int ans=0;
	for(int i=0;i<=N*2;++i)
	{
		if(oc[i].size()==1) continue;
		int temp=oc[i].size()-1;
		if(i-k>=-N&&i-k<=N) temp+=(oc[i-k].size()-(upper_bound(oc[i-k].begin(),oc[i-k].end(),oc[i][oc[i].size()-1])-oc[i-k].begin()));
		for(int j=1;j<st[i].size();++j)
		{
			int l=st[i][j],r=oc[i][j],xx=i-k;
			int num=l+st[i].size()-j;
			if(oc[i][l]==r) num--;
			int num2=upper_bound(oc[xx].begin(),oc[xx].end(),oc[i][l])-oc[xx].begin();
			int num3=lower_bound(oc[xx].begin(),oc[xx].end(),r)-oc[xx].begin();
//			int rua=temp;
			temp=max(temp,num+num3-num2);
//			if(temp!=rua&&temp==5)
//			printf("%d %d %d %d %d %d %d %d\n",l,r,j,st[i].size(),num,num2,num3,temp);
		}
//		cout<<i<<" "<<temp<<endl;
		ans=max(ans,temp);
	}
	printf("%d\n",ans);
	return 0;	
}
/*
5 2
2 2 4 4 4
5

7 1
3 2 3 2 2 2 3
6

7 1
2 3 2 3 2 3 3
5

9 -100
-1 -2 1 2 -1 -2 1 -2 1
3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 132ms
memory: 224712kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 158ms
memory: 223900kb

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 115ms
memory: 224408kb

input:

7 1
2 3 2 3 2 3 3

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 124ms
memory: 223056kb

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: -100
Wrong Answer
time: 116ms
memory: 223096kb

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:

36

result:

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