QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#622176 | #6433. Klee in Solitary Confinement | Yurily# | ML | 0ms | 0kb | C++20 | 1.9kb | 2024-10-08 20:07:15 | 2024-10-08 20:07:16 |
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int a[MAX],n,k;
vector<int> g[MAX];
struct node{
int v,id;
};
queue<node> q[MAX];
node tmp[MAX];
set<int> s;
int d[MAX],tot;
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;
}
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 findx(int x){
int l=1,r=tot;
while(l<=r){
int mid=l+r>>1;
if(d[mid]==x){
return mid;
}
else{
if(d[mid]>x)
r=mid-1;
else
l=mid+1;
}
}
return -1;
}
bool cmp(node x,node y){
return x.v>y.v;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;++i){
a[i]=read();
s.insert(a[i]);
}
for(set<int>::iterator i=s.begin();i!=s.end();++i){
d[++tot]=*i;
}
for(int i=1;i<=n;++i){
g[findx(a[i])].push_back(i);
}
int ans=0;
for(int i=1;i<=tot;++i){
ans=max(ans,(int)g[i].size());
if(!g[i].size()||findx(d[i]+k)==-1)
continue;
int t=findx(d[i]+k);
int cur=0;
for(auto j=g[i].begin();j!=g[i].end();++j){
// q[i].push(make_pair(cur-findf(t,*j),cur));
cur++;
tmp[cur].id=cur;
tmp[cur].v=cur-findf(t,*j);
}
sort(tmp+1,tmp+1+cur,cmp);
for(int j=1;j<=cur;++j)
q[i].push(tmp[i]);
}
for(int i=1;i<=n;++i){
int x=findx(a[i]),xk=findx(a[i]+k);
if(xk==-1)
continue;
int l=findf(x,i);
int cnt0_l_1=findf(xk,i-1);
int cnt1_l_1=findf(x,i-1);
while(!q[x].empty()&&q[x].front().id<l)
q[x].pop();
if(!q[x].empty()){
ans=max(ans,cnt0_l_1+q[x].front().v-cnt1_l_1+(int)g[xk].size());
}
}
cout<<ans;
}// 9 -100 -1 -2 1 2 -1 -2 1 -2 1
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
5 2 2 2 4 4 4
output:
5