QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695778#6433. Klee in Solitary Confinements2328995024sWA 11ms50792kbC++141.3kb2024-10-31 20:46:342024-10-31 20:46:34

Judging History

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

  • [2024-10-31 20:46:34]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:50792kb
  • [2024-10-31 20:46:34]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1e6;
int n,k,a[2000005],b[2000005],ans,s[2000005];
vector<int> oc[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(),2)-oc[0].begin();
    //cout<<tt<<endl;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        oc[a[i]+N].push_back(i);
    }
    for(int i=0;i<=2*N;++i)
    {
    	int tot=0,ii=0,jj=0,j=i+k;
    	int tt=oc[i].size();
    	ans=max(ans,tt);
    	if(j<0||j>2*N) continue;
    	tot=0;
    	while(ii<oc[i].size()&&jj<oc[j].size())
    	{
    		if(oc[i][ii]<oc[j][jj]) b[++tot]=1,++ii;
    		else b[++tot]=0,++jj;
		}
		while(ii<oc[i].size()) b[++tot]=1,++ii;
		while(jj<oc[j].size()) b[++tot]=0,++jj;
		for(int w=1;w<=tot;++w) s[w]=s[w-1]+b[w];
		int temp=-2e9;
		for(int w=1;w<=tot;++w)
		{
			temp=max(temp,s[w-1]*2-w);
			int ttt=ans;
			ans=max(ans,temp+w+1-s[w]+s[tot]-s[w]);
//			if(ans!=ttt&&ans==4) printf("%d %d %d %d %d %d %d %d\n",temp,w,i,tot,s[w],s[w-1],oc[i].size(),oc[j].size());
		}
	}
    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: 11ms
memory: 50792kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 50792kb

input:

7 1
3 2 3 2 2 2 3

output:

5

result:

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