QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#754076#6433. Klee in Solitary Confinementnahida_qaqWA 0ms3624kbC++232.0kb2024-11-16 14:10:502024-11-16 14:10:52

Judging History

你现在查看的是最新测评结果

  • [2024-11-16 14:10:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3624kb
  • [2024-11-16 14:10:50]
  • 提交

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'