QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691117 | #5147. Stack Sort | tsai# | WA | 0ms | 54588kb | C++14 | 1.6kb | 2024-10-31 09:57:54 | 2024-10-31 09:57:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000050;
const int mod=1000000;
int a[N]={0};
int vis[2*mod+5000]={0};
vector<int>v[N];//下标
vector<int>num;
int lower(int need,int x){
int ans=-1;
int l=0,r=v[need].size()-1;
while(l<=r){
int mid=(l+r)/2;
if(v[need][mid]<x){
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
return ans;
}
int upper(int need,int x){
int ans=v[need].size();
int l=0,r=v[need].size()-1;
while(l<=r){
int mid=(l+r)/2;
if(v[need][mid]>x){
r=mid-1;
ans=mid;
}else{
l=mid+1;
}
}
return ans;
}
void solve(){
int n,k;scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i]=x+mod;
num.push_back(x+mod);//出现过那些数字
v[x+mod].push_back(i);
}
int ans=0;
for(auto x:num){
ans=max(ans,(int)v[x].size());
}
if(k==0){
cout<<ans;
return;
}
for(auto x:num){
if(vis[x]==1) continue;
int need=x-k;
vis[x]=1;
for(int i=0;i<v[x].size();i++){
if(need<0||need>2000005||v[need].size()==0)continue;
int aa=lower(need,v[x][i]);//区间最右need
int c1=lower(x,v[need][0]);
int d1=upper(x,v[need][aa]);
aa++;//前面有几个
ans=max(ans,aa+(int)v[x].size()-(d1-c1-1));//改前面
int bb=v[need].size()-aa;//后面有几个
c1=lower(x,v[need][aa]);
d1=upper(x,v[need][v[need].size()-1]);
ans=max(ans,bb+(int)v[x].size()-(d1-c1-1));//改后面
}
}
printf("%d",ans);
return ;
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--){
solve();
if(t) printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 54588kb
input:
3 3 1 2 3 3 3 2 1 5 1 4 2 5 3
output:
1
result:
wrong answer 1st numbers differ - expected: '3', found: '1'