QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#754076 | #6433. Klee in Solitary Confinement | nahida_qaq | WA | 0ms | 3624kb | C++23 | 2.0kb | 2024-11-16 14:10:50 | 2024-11-16 14:10:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define pb push_back
#define ff first
#define ss second
typedef pair<int, int> PII;
const int N = 1000007;
const int inf = 1e18;
const int mod = 1e9+7;
mt19937_64 rng(time(0));
int a[N];
unordered_map<int,int>vis;
unordered_map<int,vector<int>>v;
void solve() {
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
v[a[i]].pb(i);
}
int ans=0;
if(k==0){
for(auto i:v){
int tt=i.ss.size();
ans=max(ans,tt);
}
cout<<ans<<'\n';
return;
}
for(int i=1;i<=n;i++){
if(vis[a[i]])continue;
vis[a[i]]=1;
int x=a[i],y=a[i]-k;
if(!v[y].size()){
int z=v[x].size();
ans=max(ans,z);
continue;
}
vector<PII>cnt;
for(auto j:v[x])cnt.pb({j,1});
for(auto j:v[y])cnt.pb({j,2});
sort(cnt.begin(),cnt.end());
vector<int>pr1(cnt.size()+1);
vector<int>pr2(cnt.size()+1);
pr1[0]=(cnt[0].ss==1);
pr2[0]=(cnt[0].ss==2);
for(int j=1;j<cnt.size();j++){
pr1[j]=pr1[j-1]+(cnt[j].ss==1);
pr2[j]=pr2[j-1]+(cnt[j].ss==2);
}
int l=0;
int sum=0;
for(int j=0;j<cnt.size();j++){
if(cnt[j].ss==1)sum--;
else sum++;
if(sum<0)sum=0;
if(sum==1){
l=j;
}
if(cnt[j].ss==2&&(j==cnt.size()-1)){
int tmp=0;
tmp+=pr2[j];
if(l)tmp+=pr1[l-1]-pr2[l-1];
tmp+=pr1[cnt.size()-1]-pr1[j];
// if(tmp>ans)cout<<l<<' '<<j<<'\n';
ans=max(ans,tmp);
}
}
}
cout<<ans<<'\n';
}
signed main() {
ios;
int _ = 1;
//cin >> _;
while (_--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3624kb
input:
5 2 2 2 4 4 4
output:
2
result:
wrong answer 1st numbers differ - expected: '5', found: '2'