QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#703835	#7904. Rainbow Subarray	wyh123	WA	131ms	6604kb	C++20	2.7kb	2024-11-02 18:39:01	2024-11-02 18:39:03

Judging History

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

[2024-11-02 18:39:03]
评测

测评结果：WA
用时：131ms
内存：6604kb

查看

[2024-11-02 18:39:01]
提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10;
int a[N];

struct mycmp{
    bool operator() (const int &a, const int &b) const {
        return a > b;
    }
};

multiset<int, mycmp> minn;
multiset<int> maxn;

void solve () {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] -= i;
    }

    int ans = 0, shang = 0, xia = 0, l = 1;
    for (int r = 1; r <= n; r ++) {
        maxn.insert(a[r]);
        shang += a[r];
        while (maxn.size() > minn.size() + 1) {
            int p = *maxn.begin(); maxn.erase(maxn.begin());
            shang -= p;
            minn.insert(p);
            xia += p;
        }

        while (minn.size() > maxn.size()) {
            int p = *minn.begin(); minn.erase(minn.begin());
            xia -= p;
            maxn.insert(p);
            shang += p;
        }

        while (minn.size() > 0 && *maxn.begin() < *minn.begin()) {
            int p = *maxn.begin();
            int s = *minn.begin();
            maxn.erase(maxn.begin()), minn.erase(minn.begin());
            shang -= p, xia -= s;
            maxn.insert(s), minn.insert(p);
            shang += s, xia += p;
        }

        while ((shang - *maxn.begin() * maxn.size()) + (*maxn.begin() * minn.size() - xia) > k) {
            if (a[l] >= *maxn.begin()) {
                maxn.erase(a[l]); shang -= a[l];
            } else {
                minn.erase(a[l]); xia -= a[l];
            }

            while (maxn.size() > minn.size() + 1) {
                int p = *maxn.begin(); maxn.erase(maxn.begin());
                shang -= p;
                minn.insert(p);
                xia += p;
            }

            while (minn.size() > maxn.size()) {
                int p = *minn.begin(); minn.erase(minn.begin());
                xia -= p;
                maxn.insert(p);
                shang += p;
            }

            while (minn.size() > 0 && *maxn.begin() < *minn.begin()) {
                int p = *maxn.begin();
                int s = *minn.begin();
                maxn.erase(maxn.begin()), minn.erase(minn.begin());
                shang -= p, xia -= s;
                maxn.insert(s), minn.insert(p);
                shang += s, xia += p;
            }
            l ++;
        }

        ans = max(ans, r - l + 1);
    }

    cout << ans << endl;

    maxn.clear(), minn.clear();
}

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;

    cin >> t;
    while (t --) {
        solve ();
    }
    return 0;
}
/*
5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3
*/

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3668kb

input:

5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3

output:

result:

ok 5 lines

Test #2:

score: -100

Wrong Answer

time: 131ms

memory: 6604kb

input:

11102
2 167959139
336470888 134074578
5 642802746
273386884 79721198 396628655 3722503 471207868
6 202647942
268792718 46761498 443917727 16843338 125908043 191952768
2 717268783
150414369 193319712
6 519096230
356168102 262263554 174936674 407246545 274667941 279198849
9 527268921
421436316 3613460...

output:

result:

wrong answer 11002nd lines differ - expected: '517', found: '515'