QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236068#6433. Klee in Solitary Confinementucup-team1001#WA 1ms3476kbC++171.8kb2023-11-03 16:03:322023-11-03 16:03:32

Judging History

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

  • [2023-11-03 16:03:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3476kb
  • [2023-11-03 16:03:32]
  • 提交

answer

//
// Created by DELLPC on 2023/11/3.
//
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;
#define irep(i, l, r) for(int i = l; i <= r; ++ i)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define lowbit(x) x&(-x)

void solve() {
    ll ans = 0;
    int n, k;
    cin >> n >> k;
    vector<int> arr(n), ord;

    irep(i, 0, n - 1) {
        cin >> arr[i];
    }
    ord = arr;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    map<int, int> mp;
    int tot = 0;
    for (int x : ord) {
        mp[x] = tot++;
    }
    vector<vector<int>> pre(tot);
    irep(i, 0, n - 1) {
        pre[mp[arr[i]]].emplace_back(i);
    }
//    cerr << tot << endl;
    irep(i, 0, tot - 1) {
        ll sum = pre[i].size(), dt = 0;
        ans = max(ans, sum);
        //ans = max(ans,(ll) pre[i].size());

        int x = ord[i];
        int y = x - k;
        if (mp.find(y) == mp.end())continue;
        int idy = mp[y];


    //    cerr << endl << idy << endl;
        int l = -1;
        for (auto r: pre[i]) {
            int cnt =
                    upper_bound(pre[idy].begin(), pre[idy].end(), r) - upper_bound(pre[idy].begin(), pre[idy].end(), l);
            dt = max(dt, 1ll * cnt);
            l = r;
        }

        int cnt = pre[idy].end() - upper_bound(pre[idy].begin(), pre[idy].end(), l);
    //    cerr << x << ' ' << max(dt, cnt * 1ll) << ' ' << sum <<endl;
        ans = max(ans, max(dt, cnt * 1ll) + sum);
    }
    cout << ans;
}

/*
 *
 *
5 2
2 2 4 4 4

7 1
3 2 3 2 2 2 3



7 1
2 3 2 3 2 3 3

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

 */

int main() {
    IOS
    int t = 1;

    while (t--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 2
2 2 4 4 4

output:

5

result:

ok 1 number(s): "5"

Test #2:

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

input:

7 1
3 2 3 2 2 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

7 1
2 3 2 3 2 3 3

output:

5

result:

ok 1 number(s): "5"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3392kb

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: 0ms
memory: 3476kb

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'