QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694187#6433. Klee in Solitary Confinements2328995024sWA 126ms222660kbC++141.8kb2024-10-31 17:26:322024-10-31 17:26:35

Judging History

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

  • [2024-10-31 17:26:35]
  • 评测
  • 测评结果:WA
  • 用时:126ms
  • 内存:222660kb
  • [2024-10-31 17:26:32]
  • 提交

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;
        int temp=oc[i].size()-1;
        if(i-k>=0&&i-k<=2*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: 124ms
memory: 222516kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 126ms
memory: 222572kb

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 125ms
memory: 222660kb

input:

7 1
2 3 2 3 2 3 3

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 111ms
memory: 222656kb

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: 222592kb

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'