QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305973#7904. Rainbow SubarrayNicolas125841WA 147ms6652kbC++175.5kb2024-01-16 07:06:042024-01-16 07:06:05

Judging History

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

  • [2024-06-09 00:00:26]
  • hack成功，自动添加数据
  • (/hack/652)
  • [2024-01-16 07:06:05]
  • 评测
  • 测评结果：WA
  • 用时：147ms
  • 内存：6652kb
查看
  • [2024-01-16 07:06:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define ABS(x) ((x) > 0 ? (x) : -(x))

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while(t--) {
        int n;
        cin >> n;

        ll k;
        cin >> k;

        vi a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }

        ll used = 0, shift = 0, abs = 0, ans = 1;
        vector<ll> srel;
        map<ll, ll> below, middle, above;

        abs = a[0];
        middle[0]++;
        srel.push_back(0);

        for(ll l = -1, r = 1; r < n; r++) {
            ll diff = abs + 1 - a[r];

            if(diff > 0) {
                above[diff - shift]++;
                used += diff;
                abs++;

                srel.push_back(diff - shift);

                if((ll)above.size() - (ll)below.size() - (ll)middle.size() > 0) {
                    ll delta = above.begin()->first + shift;
                    
                    abs -= delta;
                    shift -= delta;
                    used -= ((ll)above.size() - (ll)below.size() - (ll)middle.size()) * delta;

                    if(middle.size()) {
                        below[middle.begin()->first] += middle.begin()->second;
                        middle.clear();
                    }

                    middle[above.begin()->first] += above.begin()->second;
                    above.erase(above.begin());
                }

                while(used > k) {
                    l++;

                    used -= ABS(srel[l] + shift);

                    if(srel[l] + shift > 0) {
                        above[srel[l]]--;

                        if(!above[srel[l]])
                            above.erase(srel[l]);
                    } else if(srel[l] + shift == 0) {
                        middle[srel[l]]--;

                        if(!middle[srel[l]])
                            middle.erase(srel[l]);
                    } else {
                        below[srel[l]]--;

                        if(!below[srel[l]])
                            below.erase(srel[l]);
                    }

                    if((ll)above.size() - (ll)below.size() - (ll)middle.size() > 0) {
                        ll delta = above.begin()->first + shift;
                        
                        abs -= delta;
                        shift -= delta;
                        used -= ((ll)above.size() - (ll)below.size() - (ll)middle.size()) * delta;

                        if(middle.size()) {
                            below[middle.begin()->first] += middle.begin()->second;
                            middle.clear();
                        }

                        middle[above.begin()->first] += above.begin()->second;
                        above.erase(above.begin());
                    }
                }
            } else if(diff == 0) {
                above[-shift]++;
                abs++;
            } else {                
                below[diff - shift]++;
                used -= diff;
                abs++;

                srel.push_back(diff - shift);

                if((ll)below.size() - (ll)above.size() - (ll)middle.size() > 0) {
                    ll delta = below.rbegin()->first + shift;
                    
                    abs -= delta;
                    shift -= delta;
                    used -= ((ll)below.size() - (ll)above.size() - (ll)middle.size()) * ABS(delta);

                    if(middle.size()) {
                        above[middle.begin()->first] += middle.begin()->second;
                        middle.clear();
                    }

                    middle[below.rbegin()->first] += below.rbegin()->second;
                    below.erase(below.rbegin()->first);
                }

                while(used > k) {
                    l++;

                    used -= ABS(srel[l] + shift);

                    if(srel[l] + shift > 0) {
                        above[srel[l]]--;

                        if(!above[srel[l]])
                            above.erase(srel[l]);
                    } else if(srel[l] + shift == 0) {
                        middle[srel[l]]--;

                        if(!middle[srel[l]])
                            middle.erase(srel[l]);
                    } else {
                        below[srel[l]]--;

                        if(!below[srel[l]])
                            below.erase(srel[l]);
                    }

                    if((ll)below.size() - (ll)above.size() - (ll)middle.size() > 0) {
                        ll delta = below.rbegin()->first + shift;
                        
                        abs -= delta;
                        shift -= delta;
                        used -= ((ll)below.size() - (ll)above.size() - (ll)middle.size()) * ABS(delta);

                        if(middle.size()) {
                            above[middle.begin()->first] += middle.begin()->second;
                            middle.clear();
                        }

                        middle[below.rbegin()->first] += below.rbegin()->second;
                        below.erase(below.rbegin()->first);
                    }
                }
            }

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

        cout << ans << "\n";
    }
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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:

4
3
5
1
1

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 147ms
memory: 6652kb

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:

1
4
3
2
6
5
7
2
4
1
4
1
1
3
2
2
7
8
7
7
1
7
6
2
4
3
1
6
7
7
3
4
3
9
3
8
6
6
3
1
6
3
1
2
4
6
4
6
4
1
4
7
1
6
3
5
6
6
1
7
5
3
1
6
4
5
3
2
2
6
2
3
10
1
4
3
2
4
5
1
7
5
5
5
8
5
3
6
3
5
5
8
5
4
5
2
1
5
2
3
3
4
8
1
3
1
2
2
8
3
1
6
8
1
8
4
5
6
6
8
4
8
3
2
8
4
5
6
2
6
2
4
1
5
4
5
3
2
4
1
2
1
4
5
8
3
7
3
3
3...

result:

wrong answer 10357th lines differ - expected: '12', found: '11'
English 繁體中文 简体中文

Server Time: 2024-12-03 07:42:56 | OpenSource Project