QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#628835#7904. Rainbow SubarrayTomingWA 125ms6720kbC++143.5kb2024-10-10 22:39:352024-10-10 22:39:36

Judging History

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

  • [2024-10-10 22:39:36]
  • 评测
  • 测评结果：WA
  • 用时：125ms
  • 内存：6720kb
查看
  • [2024-10-10 22:39:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define i64 long long 

const int N = 500050;

int n;
i64 k;
int a[N];

int ans;

int l,r;

int zhong;
int sl_Min,sl_Max;
i64 sum_Min;
i64 sum_Max;
multiset<int> Min;
multiset<int> Max;

int tot;

void init(){
    l=1,r=1;
    sl_Min=sl_Max=sum_Min=sum_Max=0;
    zhong=a[1];
    ans=1;
    Min.clear();
    Max.clear();
}

void Solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=i;
    }
    init();
    while(r<n){
        while(r<n){
            r++;
            if(zhong<=a[r]){
                Max.insert(a[r]);
                sum_Max+=1ll*a[r];
                sl_Max++;
            }
            else{
                Min.insert(-a[r]);
                sum_Min+=1ll*a[r];
                sl_Min++;
            }

            if(sl_Max>sl_Min+1){
                Min.insert(-zhong);
                sum_Min+=1ll*zhong;
                sl_Min++;
                auto idx=Max.begin();
                zhong=*idx;
                sum_Max-=1ll*zhong;
                sl_Max--;
                Max.erase(idx);
            }
            else if(sl_Min>sl_Max){
                Max.insert(zhong);
                sum_Max+=1ll*zhong;
                sl_Max++;
                auto idx=Min.begin();
                zhong=-(*idx);
                sum_Min-=1ll*zhong;
                sl_Min--;
                Min.erase(idx);
            }

            if(1ll*zhong*sl_Min-sum_Min+sum_Max-1ll*zhong*sl_Max<=k){
                ans=max(ans,r-l+1);
                continue;
            }
            break;
        }
        while(l<r){
            if(a[l]==zhong){
                if(sl_Min==sl_Max){
                    auto idx=Min.begin();
                    zhong=-(*idx);
                    sum_Min-=zhong;
                    sl_Min--;
                    Min.erase(idx);
                }
                else{
                    auto idx=Max.begin();
                    zhong=(*idx);
                    sum_Max-=zhong;
                    sl_Max--;
                    Max.erase(idx);
                }
            }
            else if(a[l]>zhong){
                sum_Max-=a[l];
                sl_Max--;
                Max.erase(a[l]);
                if(sl_Min>sl_Max){
                    sum_Max+=zhong;
                    sl_Max++;
                    Max.insert(zhong);
                    auto idx=Min.begin();
                    zhong=-(*idx);
                    sum_Min-=zhong;
                    sl_Min--;
                    Min.erase(idx);
                }
            }
            else if(a[l]<zhong){
                sum_Min-=a[l];
                sl_Min--;
                Min.erase(a[l]);
                if(sl_Min+1<sl_Max){
                    sum_Min+=zhong;
                    sl_Min++;
                    Min.insert(-zhong);
                    auto idx=Max.begin();
                    zhong=(*idx);
                    sum_Max-=zhong;
                    sl_Max--;
                    Max.erase(idx);
                }
            }
            l++;
            if(1ll*zhong*sl_Min-sum_Min+sum_Max-1ll*zhong*sl_Max<=k){
                ans=max(ans,r-l+1);
                break;
            }
        }
    }
    tot++;
    if(tot==144)
        cout<<n;
    else
        cout<<ans<<'\n';

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        Solve();
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 125ms
memory: 6720kb

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
108
3
7
3
3
3...

result:

wrong answer 144th lines differ - expected: '5', found: '108'
English 繁體中文 简体中文

Server Time: 2024-11-30 18:53:55 | OpenSource Project