QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #628847 | #7904. Rainbow Subarray | Toming | WA | 125ms | 7044kb | C++23 | 3.5kb | 2024-10-10 22:42:19 | 2024-10-10 22:42:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define int 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;
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;
}
}
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)
Solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
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: 7044kb
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 4 8 3 7 3 3 3...
result:
wrong answer 144th lines differ - expected: '5', found: '4'