QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638012#6433. Klee in Solitary Confinement333zhanWA 60ms112520kbC++201.8kb2024-10-13 14:38:502024-10-13 14:38:51

Judging History

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

  • [2024-10-13 14:38:51]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:112520kb
  • [2024-10-13 14:38:50]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1E6;
constexpr int inf = 1E9;

void solve () {
    int n, k;
    cin >> n >> k;

    vector <int> a (n + 1);
    vector <vector <int>> id2 (N * 2 + 1);
    for (int i = 0; i <= N * 2; i ++) {
        id2[i].push_back (0);
    }
    map <int, int> mp;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] += N;
        mp[a[i]] ++;
        id2[a[i]].push_back (i);
        if (a[i] + k >= 0 && a[i] + k <= 2 * N) {
            id2[a[i] + k].push_back (i);
        }
    }

    int ans = 0;

    int ttt = 0;
    for (auto [x, y] : mp) {
        ans = max (ans, y);
    }
    for (int i = 0; i <= N * 2; i ++) {
        // ttt += id2[i].size ();
        if (id2[i].size () == 1) {
            continue;
        }
        const int m = id2[i].size () - 1;
        vector <int> c (m + 1);
        vector <int> pre (m + 1), suf (m + 2);
        for (int j = 1; j <= m; j ++) {
            c[j] = c[j - 1] + (a[id2[i][j]] == i ? -1 : 1);
            pre[j] = pre[j - 1] + (a[id2[i][j]] == i);
        }
        vector <int> maxx (m + 2, -inf);
        for (int j = m; j >= 1; j --) {
            suf[j] = suf[j + 1] + (a[id2[i][j]] == i);
            maxx[j] = max (maxx[j + 1], c[j] + suf[j + 1]);
        }
        for (int j = 1; j <= m; j ++) {
            ans = max (ans, maxx[j] - c[j - 1] + pre[j - 1]);
        }
        // ttt += c.size ();
        // ttt += pre.size ();
        // ttt += suf.size ();
        // ttt += maxx.size ();
    }
    // cerr << ttt << '\n';

    cout << ans << '\n';
}

signed main () {
    ios::sync_with_stdio (false);
    cin.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: 55ms
memory: 112436kb

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 60ms
memory: 112520kb

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 44ms
memory: 112456kb

input:

7 1
2 3 2 3 2 3 3

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 52ms
memory: 112424kb

input:

9 -100
-1 -2 1 2 -1 -2 1 -2 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

score: -100
Wrong Answer
time: 60ms
memory: 112516kb

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:

36

result:

wrong answer 1st numbers differ - expected: '37', found: '36'