QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#621993 | #6433. Klee in Solitary Confinement | Yurily# | ML | 0ms | 0kb | C++14 | 1.8kb | 2024-10-08 19:14:35 | 2024-10-08 19:14:36 |
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6;
int a[MAX+5],n,k;
vector<int> g[MAX*2+5];
struct node{
int v,id;
};
queue<node> q[MAX*2+5];
node tmp[MAX+5];
int findf(int u,int x){
int l=0,r=(int)g[u].size()-1,res=-1;
while(l<=r){
int mid=l+r>>1;
if(g[u][mid]<=x){
res=mid;
l=mid+1;
}
else
r=mid-1;
}
return res+1;
}
bool cmp(node x,node y){
return x.v>y.v||x.v==y.v&&x.id<y.id;
}
int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-'){
f = -1;
}
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i){
a[i]=read();
g[a[i]+MAX].push_back(i);
}
int ans=0;
for(int i=0;i<=MAX*2;++i){
ans=max(ans,(int)g[i].size());
if(!g[i].size()||i+k>MAX*2||i+k<0)
continue;
for(int j=0;j<g[i].size();++j){
tmp[j+1].id=j+1;
tmp[j+1].v=j+1-findf(i+k,g[i][j]);
}
sort(tmp+1,tmp+1+g[i].size(),cmp);
for(int j=1;j<=(int)g[i].size();++j){
if(tmp[j].v<=0)
break;
q[i].push(tmp[j]);
}
// cout<<i-MAX<<" ";
// for(int j=1;j<=(int)g[i].size();++j){
// cout<<tmp[j].id<<" "<<tmp[j].v<<" ";
// }
// cout<<endl;
}
// cout<<ans<<endl;
for(int i=1;i<=n;++i){
if(a[i]+k>MAX||a[i]+k<-MAX)
continue;
int l=findf(a[i]+MAX,i);
int cnt0_l_1=findf(a[i]+k+MAX,i-1);
int cnt1_l_1=findf(a[i]+MAX,i-1);
// cout<<i<<" "<<l<<" "<<cnt0_l_1<<endl;
while(!q[a[i]+MAX].empty()&&q[a[i]+MAX].front().id<l)
q[a[i]+MAX].pop();
if(!q[a[i]+MAX].empty()){
ans=max(ans,cnt0_l_1+q[a[i]+MAX].front().v-cnt1_l_1+(int)g[a[i]+k+MAX].size());
}
else{
ans=max(ans,cnt0_l_1-cnt1_l_1+(int)g[a[i]+k+MAX].size());
}
}
cout<<ans;
}
详细
Test #1:
score: 0
Memory Limit Exceeded
input:
5 2 2 2 4 4 4
output:
5