QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#252734 | #6433. Klee in Solitary Confinement | limpid | WA | 4ms | 32624kb | C++14 | 2.1kb | 2023-11-16 09:16:26 | 2023-11-16 09:16:26 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<ctime>
#include<map>
#define pii pair<int,int>
#define pb push_back
#define LL long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read(){
int f=1,ans=0; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return f*ans;
}
const int MAXN=1e6+11;
int N,A[MAXN],tmp[MAXN],K; map<int,int> Ma;
vector<int> vec[MAXN];
int sta[MAXN],Maxn;
int main(){
//freopen("1.in","r",stdin);
N=read(),K=read(); for(int i=1;i<=N;i++) A[i]=tmp[i]=read();
sort(tmp+1,tmp+N+1); int M=unique(tmp+1,tmp+N+1)-tmp-1;
for(int i=1;i<=M;i++) Ma[tmp[i]]=i;
for(int i=1;i<=N;i++) A[i]=lower_bound(tmp+1,tmp+M+1,A[i])-tmp,vec[A[i]].pb(i);
//for(int i=1;i<=N;i++) cerr<<A[i]<<" ";cerr<<endl;
for(int i=1;i<=M;i++){
if(Ma[tmp[i]-K]==0){Maxn=max(Maxn,(int)vec[i].size()); continue;}
int id=Ma[tmp[i]-K];
int p1=0,p2=0; sta[0]=0;
while(p1!=vec[i].size()&&p2!=vec[id].size()){
if(vec[i][p1]<vec[id][p2]) sta[++sta[0]]=1,p1++;
else sta[++sta[0]]=0,p2++;
}
//cerr<<"p1:"<<p1<<" "<<vec[i].size()<<" "<<i<<" "<<A[1]<<endl;
while(p1!=vec[i].size()) sta[++sta[0]]=1,p1++;
while(p2!=vec[id].size()) sta[++sta[0]]=0,p2++;
int Sum=0;
//cerr<<tmp[i]<<" "<<tmp[id]<<endl;
//for(int j=1;j<=sta[0];j++) cerr<<sta[j]<<" ";cerr<<endl;
for(int j=1;j<=sta[0];j++) Sum+=sta[j];//0->1 1->-1
for(int j=1;j<=sta[0];j++){
if(sta[j]==0) sta[j]=1;
else sta[j]=-1;
}
int nmaxn=0,maxsum=0;
for(int j=1;j<=sta[0];j++){
nmaxn=max(nmaxn,maxsum+sta[j]);
maxsum=max(maxsum+sta[j],sta[j]);
maxsum=max(maxsum,0);
}
Sum+=nmaxn; Maxn=max(Maxn,Sum);
//printf("%d\n",Sum);
}printf("%d\n",Maxn);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 32624kb
input:
5 2 2 2 4 4 4
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 4ms
memory: 32480kb
input:
7 1 3 2 3 2 2 2 3
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 4ms
memory: 30428kb
input:
7 1 2 3 2 3 2 3 3
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 0ms
memory: 32408kb
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: 0ms
memory: 32476kb
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: 0
Accepted
time: 0ms
memory: 30436kb
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:
40
result:
ok 1 number(s): "40"
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 30448kb
input:
200 0 451272 -1000000 677452 677452 0 18908 451272 677452 -233144 677452 451272 18908 -1000000 18908 -1000000 0 451272 0 -233144 677452 1000000 451272 1000000 18908 -1000000 0 -233144 451272 1000000 18908 677452 0 677452 0 677452 1000000 -233144 18908 451272 -1000000 -233144 18908 1000000 0 0 -23314...
output:
36
result:
wrong answer 1st numbers differ - expected: '35', found: '36'