QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622081 | #6433. Klee in Solitary Confinement | Yurily# | WA | 8ms | 58344kb | C++14 | 1.7kb | 2024-10-08 19:47:44 | 2024-10-08 19:47:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int a[MAX],n,k;
vector<int> g[MAX];
priority_queue<pair<int,int> > q[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;
}
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);
for(int j=0;j<g[i].size();++j){
q[i].push(make_pair(j+1-findf(t,g[i][j]),j+1));
}
}
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].top().second<l||q[x].top().first<=0))
q[x].pop();
if(!q[x].empty()){
ans=max(ans,cnt0_l_1+q[x].top().first-cnt1_l_1+(int)g[xk].size());
}
else{
ans=max(ans,cnt0_l_1-cnt1_l_1+(int)g[xk].size());
}
}
cout<<ans;
}// 9 -100 -1 -2 1 2 -1 -2 1 -2 1
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 58260kb
input:
5 2 2 2 4 4 4
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 3ms
memory: 58320kb
input:
7 1 3 2 3 2 2 2 3
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 7ms
memory: 58320kb
input:
7 1 2 3 2 3 2 3 3
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 7ms
memory: 58316kb
input:
9 -100 -1 -2 1 2 -1 -2 1 -2 1
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: 0
Accepted
time: 8ms
memory: 58324kb
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:
37
result:
ok 1 number(s): "37"
Test #6:
score: -100
Wrong Answer
time: 8ms
memory: 58344kb
input:
200 -454379 -385892 454379 -1000000 373644 -665078 -1000000 -1000000 454379 0 1000000 373644 -1000000 1000000 -385892 -1000000 373644 0 -665078 0 -665078 -1000000 -665078 -385892 -665078 -385892 454379 -665078 -385892 -1000000 454379 1000000 -385892 373644 454379 -1000000 -385892 -1000000 -385892 -1...
output:
48
result:
wrong answer 1st numbers differ - expected: '40', found: '48'