QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798196#5417. Chat ProgramvwxyzWA 1629ms10248kbC++232.2kb2024-12-04 09:35:312024-12-04 09:35:32

Judging History

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

  • [2024-12-04 09:35:32]
  • 评测
  • 测评结果:WA
  • 用时:1629ms
  • 内存:10248kb
  • [2024-12-04 09:35:31]
  • 提交

answer

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;
using ll = long long;

class MultiSet {
    multiset<ll> ms;

public:
    void push(ll x) {
        ms.insert(x);
    }

    void discard(ll x) {
        auto it = ms.find(x);
        if (it != ms.end()) {
            ms.erase(it);
        }
    }

    ll top() {
        if (ms.empty()) return LLONG_MIN;
        return *ms.rbegin(); // 最大値を返す
    }

    void pop() {
        if (!ms.empty()) {
            ms.erase(prev(ms.end())); // 最大値を削除
        }
    }

    size_t size() const {
        return ms.size();
    }
};

bool is_ok(ll x, ll N, ll K, ll M, ll C, ll D, const vector<ll>& A) {
    bool retu = false;
    vector<int> cnt(N + 1, 0);
    for (ll i = 1; i <= N; ++i) {
        cnt[i] = cnt[i - 1] + (A[i - 1] >= x ? 1 : 0);
    }

    MultiSet MS;
    for (ll l = N - M; l >= 0; --l) {
        ll r = l + M;
        if (l == N - M) {
            for (ll n = l; n < r; ++n) {
                MS.push(A[n] + C + n * D);
            }
        } else {
            if (A[r - 1] + C + r * D < x + D * l) {
                MS.discard(A[r - 1] + C + r * D);
            }
            MS.push(A[l] + C + l * D);
        }
        while (MS.size() > 0 && MS.top() >= x + D * (l - 1)) {
            MS.pop();
        }
        ll c = cnt[l] + cnt[N] - cnt[r];
        if (D * (l - 1) < LLONG_MAX) {
            c += r - l - MS.size();
        }
        if (c >= K) {
            retu = true;
        }
    }
    return retu;
}

ll Bisect_Int(ll ok, ll ng, function<bool(ll)> is_ok) {
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
        if (is_ok(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

int main() {
    ll N, K, M, C, D;
    cin >> N >> K >> M >> C >> D;
    vector<ll> A(N);
    for (ll i = 0; i < N; ++i) {
        cin >> A[i];
    }

    const ll inf = 1LL << 50;
    auto is_ok_func = [&](ll x) {
        return is_ok(x, N, K, M, C, D, A);
    };
    ll ans = Bisect_Int(0, inf, is_ok_func);
    cout << ans << endl;

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3508kb

input:

6 4 3 1 2
1 1 4 5 1 4

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

7 3 2 4 0
1 9 1 9 8 1 0

output:

9

result:

ok 1 number(s): "9"

Test #3:

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

input:

8 3 5 0 0
2 0 2 2 1 2 1 8

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 997ms
memory: 10196kb

input:

200000 200000 100000 0 1000000000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 1629ms
memory: 10248kb

input:

200000 1 100000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...

output:

100002000000000

result:

wrong answer 1st numbers differ - expected: '100001000000000', found: '100002000000000'