QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265979#6433. Klee in Solitary ConfinementwendadawenWA 1ms3464kbC++143.7kb2023-11-25 23:51:062023-11-25 23:51:07

Judging History

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

  • [2023-11-25 23:51:07]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3464kb
  • [2023-11-25 23:51:06]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<=b;++i)
using ll = long long;
using namespace std;

void solve(){
    int n, k; cin >> n >> k;
    vector<int>a(n+1);
    int ans=0;
    map<int,vector<int>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(!q.count(a[i]))
        q[a[i]].push_back(0);
        q[a[i]].push_back(i);
    }
    for(auto it:q)
    {
        int x=it.first;
        q[x].push_back(n+1);
    }
    for(auto it:q)
    {
        int x=it.first;
        auto vx=it.second;
        int sx=vx.size();
        vector<int>c;
        if(q.count(x-k))
        {
            auto vy=q[x-k];
            int sy=vy.size();
            int l=1,r=1;
            for(int i=1;i<sx;i++)
            {
                int lx=vx[i-1],rx=vx[i];
                c.push_back(-1);
                // cout<<lx<<' '<<rx<<' ';
                while(r<sy&&vy[r]<=rx)
                r++;
                while(l<sy&&vy[l]<lx)
                l++;
                // cout<<l<<' '<<r<<'\n';
                c.push_back(r-l);
            }
            int nn = c.size();
            vector<int> dp(nn+1);
            int mx = 0;
            for(int i = 0; i < nn; ++ i) {
                dp[i+1] = max({0LL, dp[i]+c[i], c[i]});
                mx = max(mx,dp[i+1]);
            }
            // cout<<mx<<'\n';
            ans=max(ans,(int)(vx.size()-2)+mx);
        }
        else ans=max(ans,(int)(vx.size()-2));
    }
            cout<<ans<<'\n';
    // int base = 1e6;
    // vector<int> a(n+1);
    // unordered_map<int, int> mp;
    // vector<int> pos[(int)2e6+10];
    // for(int i = 1; i <= n; ++ i) {
    //     cin >> a[i]; a[i] += base;
    //     int x = a[i];
    //     if(!mp.count(x)) pos[x].push_back(1);
    //     mp[x] = i;
    //     pos[x].push_back(i);
    // }
    // for(auto&[x, p]: mp) {
    //     pos[x].push_back(n);
    // }


    auto get = [&](int l, int r, int x)->int{

        return 0;
    };
    // vector<int> a(n + 1);
    // unordered_map<int, int> c;
    // int maxx = 0;
    // vector<int> maxn;
    // for(int i = 1; i <= n; ++i) {
    //     cin >> a[i];
    //     c[a[i]]++;
    //     if(c[a[i]] > maxx) {
    //         maxx = c[a[i]];
    //         maxn.clear();
    //         maxn.push_back(a[i]);
    //     } else if(c[a[i]] == maxx) {
    //         maxn.push_back(a[i]);
    //     }
    // }
    // int ans = 0;
    // auto check = [&](int x) -> int {
    //     int re = x - k;
    //     if(c[re] == 0) return 0;
    //     int pre = 0;
    //     int cntp = 0;
    //     int cntn = 0;
    //     int ans = 0;
    //     // cout << x << ' ' << re << '\n';
    //     for(int i = 1; i <= n; ++i) {
    //         // cout << a[i] << ' ' << pre << ' ' << cntp << ' ' << cntn << '\n';
    //         if(a[i] == re && pre == 0) {
    //             pre = i;
    //             cntp = 1;
    //         }else if(a[i] == x && pre) {
    //             cntn++;
    //         } else if(a[i] == re && pre) {
    //             cntp++;
    //             if(cntp - cntn >= 0) {
    //                 ans = max(ans, cntp - cntn);
    //             } else {
    //                 cntp = 0;
    //                 cntn = 0;
    //                 pre = i;
    //             }
    //         }
    //     }
    //     return ans + c[x];
    // };
    // for(auto i : maxn) {
    //     ans = max(ans, check(i));
    //     cout << i << ' ' << ans << '\n';
    // }
    // cout << ans;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while( t --) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3412kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3464kb

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: 3464kb

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: 3388kb

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: 3448kb

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: 1ms
memory: 3392kb

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:

71

result:

wrong answer 1st numbers differ - expected: '35', found: '71'