QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694116 | #6433. Klee in Solitary Confinement | s2328995024s | WA | 158ms | 224712kb | C++14 | 1.6kb | 2024-10-31 17:17:30 | 2024-10-31 17:17:32 |
Judging History
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'