QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300810 | #7904. Rainbow Subarray | __jk__# | WA | 0ms | 3616kb | C++14 | 2.3kb | 2024-01-08 20:46:12 | 2024-01-08 20:46:13 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
using rii=pair <int,pii>;
using qii=pair <pii,pii>;
using namespace __gnu_pbds;
const int mod=998244353LL;
void solve(){
int n,k;
cin>>n>>k;
int a[n+1];
for (int i=1; i<=n; i++) cin>>a[i];
for (int i=1; i<=n; i++) a[i]-=i;
int l=1,r=n;
while (l<r){
int mid=(l+r+1)/2;
bool ok=0;
int sums=0,suml=0;
multiset <int> sm,la;
for (int i=1; i<=mid; i++){
sm.insert(a[i]);
sums+=a[i];
}
while (sm.size()>mid/2){
auto it=(--sm.end());
sums-=(*it);
suml+=(*it);
la.insert(*it);
sm.erase(it);
}
if (suml-mid/2*(*la.begin())+(mid-mid/2)*(*la.begin())-sums<=k) ok=1;
for (int i=2; i+mid-1<=n; i++){
auto it=sm.find(a[i-1]);
if (it!=sm.end()){
sums-=a[i-1];
sm.erase(it);
} else {
suml-=a[i-1];
la.erase(la.find(a[i-1]));
}
if (!la.empty()&&a[i+mid-1]>=(*la.begin())){
la.insert(a[i+mid-1]);
suml+=a[i+mid-1];
} else {
sm.insert(a[i+mid-1]);
sums+=a[i+mid-1];
}
while (sm.size()<mid/2){
auto it=la.begin();
sums+=(*it);
suml-=(*it);
sm.insert(*it);
la.erase(it);
}
while (sm.size()>mid/2){
auto it=(--sm.end());
sums-=(*it);
suml+=(*it);
la.insert(*it);
sm.erase(it);
}
if (suml-mid/2*(*la.begin())+(mid-mid/2)*(*la.begin())-sums<=k){
ok=1;
break;
}
}
if (ok) l=mid;
else r=mid-1;
}
cout<<l<<'\n';
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t=1;
cin>>t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3616kb
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 2 5 1 1
result:
wrong answer 2nd lines differ - expected: '3', found: '2'