QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#620713	#7904. Rainbow Subarray	dzycuc	TL	0ms	3620kb	C++14	3.5kb	2024-10-07 20:43:18	2024-10-07 20:43:19

Judging History

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

[2024-10-07 20:43:19]
评测

测评结果：TL
用时：0ms
内存：3620kb

查看

[2024-10-07 20:43:18]
提交

answer

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#define ll long long
using namespace std;

ll a[500005];
ll ti,n,k;
priority_queue<ll>q1;
priority_queue<ll,vector<ll>,greater<ll>>q2;
map<ll,ll>mp1,mp2;

bool ck(ll x)
{
    mp1.clear();
    mp2.clear();
    while(!q1.empty())
        q1.pop();
    while(!q2.empty())
        q2.pop();
    ll sz1=0,sz2=0;
    ll s1=0,s2=0;
    ll key=0;

    for(ll i=1;i<=x;++i)
    {
        q1.push(a[i]);
        s1+=a[i];
        ++mp1[a[i]];
    }
    while(q1.size()-q2.size()>1)
    {
        ll tp=q1.top();
        q1.pop();
        q2.push(tp);
        s1-=tp;
        s2+=tp;
        --mp1[tp];
        ++mp2[tp];
    }
    sz1=q1.size();
    sz2=q2.size();

    key=s2-s1;
    if(sz1>sz2)
    {
        key+=q1.top();
    }
    if(key<=k)
        return true;

    for(ll i=1,j=x;j<n;++i,++j)
    {
        while(mp1[q1.top()]==0)
            q1.pop();
        while(mp2[q2.top()]==0)
            q2.pop();
        if(a[i]<=q1.top())
        {
            --mp1[a[i]];
            --sz1;
            s1-=a[i];
        }
        else if(a[i]>=q2.top())
        {
            --mp2[a[i]];
            --sz2;
            s2-=a[i];
        }
        
        q1.push(a[j+1]);
        s1+=a[j+1];
        ++mp1[a[j+1]];
        ++sz1;

        while(sz1-sz2>1)
        {
            while(mp1[q1.top()]==0)
                q1.pop();
            ll tp=q1.top();
            q1.pop();
            q2.push(tp);
            s1-=tp;
            s2+=tp;

            --sz1;
            ++sz2;
            --mp1[tp];
            ++mp2[tp];
        }
        while(sz2-sz1>1)
        {
            while(mp2[q2.top()]==0)
                q2.pop();
            ll tp=q2.top();
            q2.pop();
            q1.push(tp);
            s1+=tp;
            s2-=tp;
            ++sz1;
            --sz2;
            ++mp1[tp];
            --mp2[tp];
        }

        while(mp1[q1.top()]==0)
            q1.pop();
        while(mp2[q2.top()]==0)
            q2.pop();
        ll m1=q1.top();
        ll m2=q2.top();
        while(m1>m2)
        {
            q1.pop();
            q2.pop();
            q1.push(m2);
            q2.push(m1);
            s1-=m1;
            s2-=m2;
            s1+=m2;
            s2+=m1;
            --mp1[m1];
            --mp2[m2];
            ++mp1[m2];
            ++mp2[m1];
            while(mp1[q1.top()]==0)
                q1.pop();
            while(mp2[q2.top()]==0)
                q2.pop();
            m1=q1.top();
            m2=q2.top();
        }
        key=s2-s1;
        if(sz1>sz2)
        {
            while(mp1[q1.top()]==0)
                q1.pop();
            key+=q1.top();
        }
        if(sz2>sz1)
        {
            while(mp2[q2.top()]==0)
                q2.pop();
            key-=q2.top();
        }
        if(key<=k)
            return true;
    }
    
    return false;
}
ll f(ll l,ll r)
{
    ll mid;
    while(l<r)
    {
        mid=(l+r+1)/2;
        if(ck(mid))
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    if(ck(l))
        return l;
    else return 1;
}
int main()
{
    cin>>ti;
    while(ti--)
    {
        cin>>n>>k;
        for(ll i=1;i<=n;++i)
        {
            cin>>a[i];
            a[i]-=i;
        }
        ll ans=f(2,n);
        cout<<ans<<endl;
        
    }
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3620kb

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:

result:

ok 5 lines

Test #2:

score: -100

Time Limit Exceeded

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: