QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#637978#6433. Klee in Solitary Confinement333zhanML 0ms0kbC++201.9kb2024-10-13 14:31:542024-10-13 14:31:54

Judging History

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

  • [2024-10-13 14:31:54]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-10-13 14:31:54]
  • 提交

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>> id (N * 4 + 1);
    vector <vector <int>> id2 (N * 4 + 1);
    for (int i = 0; i <= N * 4; i ++) {
        id2[i].push_back (0);
    }
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] += N * 2;
        id[a[i]].push_back (i);
        id2[a[i]].push_back (i);
        id2[a[i] + k].push_back (i);
    }

    int ans = 0;

    for (int i = N; i <= N * 3; i ++) {
        const int m = id[i].size ();
        ans = max (ans, m);
    }
    for (int i = 0; i <= N * 4; i ++) {
        if (id2[i].empty ()) {
            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 ++) {
            // if (i == 3 + 2 * N) {
            //     cerr << j << " " << c[j] << " " << pre[j] << " " << suf[j] << '\n';   
            // }
            // if (maxx[j] - c[j - 1] + pre[j - 1] == 4) {
            //     cerr << i - 2 * N << " " << j << " " << maxx[j] << " " << c[j - 1] << " " << pre[j - 1] << "\n";
            // } 
            ans = max (ans, maxx[j] - c[j - 1] + pre[j - 1]);
        }
    }

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

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    // cin >> T;

    while (T --) {
        solve ();
    }

    return 0;
}

详细

Test #1:

score: 0
Memory Limit Exceeded

input:

5 2
2 2 4 4 4

output:

5

result: