QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #709942 | #7904. Rainbow Subarray | HQLF | WA | 941ms | 6552kb | C++20 | 2.9kb | 2024-11-04 17:33:27 | 2024-11-04 17:33:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ldb=long double;
const long long inf=0x3f3f3f3f3f3f3f3f;
const ll mod=1000000007;
int a[500010];
void solve()
{
ll n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i]-i;
}
ll l=1,r=n;
while(l<=r)
{
ll mid=(l+r)>>1;
multiset<ll>s1,s2;
ll sum1=0,sum2=0;
for(ll i=1;i<=mid;i++)
{
s1.insert(a[i]);
sum1+=a[i];
}
while(s1.size()>(mid+1)/2)
{
s2.insert(*s1.rbegin());
sum2+=*s1.rbegin();
sum1-=*s1.rbegin();
auto x=s1.end();
x--;
s1.erase(x);
}
ll md=*s1.rbegin();
ll ls1=(ll)s1.size();
ll ls2=(ll)s2.size();
ll tx=(md*ls1-sum1)+(sum2-md*ls2);
if(tx<=k)
{
l=mid+1;
continue;
}
ll f=0;
for(ll i=2,j=i+mid-1;j<=n;i++,j++)
{
ll del=a[i-1];
ll add=a[j];
if(s1.find(del)!=s1.end())
{
s1.extract(del);
sum1-=del;
}
else if(s2.find(del)!=s2.end())
{
s2.extract(del);
sum2-=del;
}
if(!s1.empty()&&add<*s1.rbegin())
{
s1.insert(add);
sum1+=add;
}
else if(!s1.empty()&&add>*s1.rbegin())
{
s2.insert(add);
sum2+=add;
}
else if(!s1.empty()&&add==*s1.rbegin())
{
s1.insert(add);
sum1+=add;
}
else if(s1.empty())
{
s1.insert(add);
}
while(s1.size()>(mid+1)/2)
{
s2.insert(*s1.rbegin());
sum1-=*s1.rbegin();
sum2+=*s1.rbegin();
auto x=s1.end();
x--;
s1.erase(x);
}
while(s1.size()<(mid+1)/2)
{
s1.insert(*s2.begin());
sum1+=*s2.begin();
sum2-=*s2.begin();
auto x=s2.begin();
s2.erase(x);
}
md=*s1.rbegin();
ls1=(ll)s1.size();
ls2=(ll)s2.size();
tx=(md*ls1-sum1)+(sum2-md*ls2);
if(tx<=k)
{
f=1;
break;
}
}
if(f==1)
{
l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",r);
}
int main()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
ll _=1;
cin>>_;
while(_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4052kb
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: 941ms
memory: 6552kb
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 1 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 1 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 1 3 10 1 4 1 2 4 5 1 7 5 5 5 8 5 3 6 3 5 5 8 5 4 5 1 1 5 1 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 1 2 4 1 2 1 4 5 8 3 7 3 3 3...
result:
wrong answer 15th lines differ - expected: '2', found: '1'