Submission #950616

#	Time	Username	Problem	Language	Result	Execution time	Memory
950616		andrei_boaca	Chorus (JOI23_chorus)	C++17	87 / 100	7031 ms	111916 KiB

chorus

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e17;
ll n,k,lga,lgb,makegood;
ll A[1000005],B[1000005],Bspate[1000005],Afata[1000005],sB[1000005];
struct date
{
    ll val,l,r;
} dp[1000005];
struct func
{
    ll a,b,p;
};
vector<pair<func,pll>> cht;
string str;
date combine(date a, date b)
{
    if(a.val<b.val)
        return a;
    if(a.val>b.val)
        return b;
    a.l=min(a.l,b.l);
    a.r=max(a.r,b.r);
    return a;
}
ll eval(func f,ll x)
{
    return f.a*x+f.b;
}
ll intersect(func f, func g)
{
    assert(f.a<g.a);
    ll x=(f.b-g.b)/(g.a-f.a);
    while(eval(f,x)>eval(g,x))
        x++;
    return x;
}
func getval(ll x)
{
    ll st=0;
    ll dr=cht.size();
    dr--;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        if(cht[mij].second.first<=x&&cht[mij].second.second>=x)
            return cht[mij].first;
        if(cht[mij].second.first>x)
            dr=mij-1;
        if(cht[mij].second.second<x)
            st=mij+1;
    }
    assert(false);
}
void addL(func f)
{
    while(!cht.empty())
    {
        func t=cht.back().first;
        ll lft=cht.back().second.first;
        ll rgt=cht.back().second.second;
        ll poz=intersect(f,t);
        if(eval(f,poz)==eval(t,poz))
        {
            if(f.p>t.p)
                poz++;
        }
        if(poz>rgt)
            break;
        if(poz<=lft)
        {
            cht.pop_back();
            continue;
        }
        bool ok=0;
        if(t.a==6)
            ok=1;
        cht.pop_back();
        rgt=poz-1;
        cht.push_back({t,{lft,rgt}});
        break;
    }
    if(cht.empty())
    {
        cht.push_back({f,{1,n}});
        return;
    }
    ll poz=cht.back().second.second;
    poz++;
    if(poz<=n)
        cht.push_back({f,{poz,n}});
}
void addR(func f)
{
    while(!cht.empty())
    {
        func t=cht.back().first;
        ll lft=cht.back().second.first;
        ll rgt=cht.back().second.second;
        ll poz=intersect(f,t);
        if(eval(f,poz)==eval(t,poz))
        {
            if(f.p<t.p)
                poz++;
        }
        if(poz>rgt)
            break;
        if(poz<=lft)
        {
            cht.pop_back();
            continue;
        }
        cht.pop_back();
        rgt=poz-1;
        cht.push_back({t,{lft,rgt}});
        break;
    }
    if(cht.empty())
    {
        cht.push_back({f,{1,n}});
        return;
    }
    ll poz=cht.back().second.second;
    poz++;
    if(poz<=n)
        cht.push_back({f,{poz,n}});
}
ll verif[1000005];
void solve(ll cost)
{
    /*for(int i=n;i>=1;i--)
    {
        bool dbg=0;
        if(i==2&&cost==4)
            dbg=1;
        dp[i]={INF,0,0};
        ll suma=0;
        ll C=0;
        int ind=i;
        for(int j=i;j<=n;j++)
        {
            while(ind<=n&&B[ind]<A[j])
            {
                suma++;
                ind++;
            }
            C+=suma;
            date a=dp[j+1];
            a.val+=C+cost;
            a.l++;
            a.r++;
            dp[i]=combine(dp[i],a);
        }
        verif[i]=dp[i].val;
    }*/
    dp[n+1]={0,0,0};
    deque<int> coada;
    coada.push_back(n+1);
    cht.clear();
    for(ll i=n;i>=1;i--)
    {
        bool dbg=0;
        if(i==2&&cost==4)
            dbg=1;
        dp[i].val=INF;
        dp[i].l=0;
        while(!coada.empty()&&B[i]<A[coada.front()])
        {
            ll j=coada.front();
            coada.pop_front();
            ll a=j;
            ll b=dp[j].val;
            ll p=dp[j].l;
            b-=a*Bspate[j];
            b-=sB[i];
            func f={a,b,p};
            addL(f);
        }
        if(!coada.empty())
        {
            dp[i].val=dp[coada.front()].val;
            dp[i].l=dp[coada.front()].l;
        }
        if(!cht.empty())
        {
            func f=getval(n-i+1);
            ll val=f.a*(n-i+1)+f.b;
            val+=sB[i-1];
            if(val<dp[i].val)
            {
                dp[i].val=val;
                dp[i].l=f.p;
            }
            else if(val==dp[i].val)
                dp[i].l=min(dp[i].l,f.p);
        }
        dp[i].l++;
        dp[i].val+=cost;
        while(!coada.empty())
        {
            int j=coada.back();
            if(dp[j].val>dp[i].val||(dp[j].val==dp[i].val&&dp[j].l>dp[i].l))
                coada.pop_back();
            else
                break;
        }
        coada.push_back(i);
    }
    coada.clear();
    cht.clear();
    coada.push_back(n+1);
    for(ll i=n;i>=1;i--)
    {
        ll aux=dp[i].val;
        dp[i].val=INF;
        dp[i].r=0;
        while(!coada.empty()&&B[i]<A[coada.front()])
        {
            ll j=coada.front();
            coada.pop_front();
            ll a=j;
            ll b=dp[j].val;
            ll p=dp[j].r;
            b-=a*Bspate[j];
            b-=sB[i];
            func f={a,b,p};
            addR(f);
        }
        if(!coada.empty())
        {
            dp[i].val=dp[coada.front()].val;
            dp[i].r=dp[coada.front()].r;
        }
        if(!cht.empty())
        {
            func f=getval(n-i+1);
            ll val=f.a*(n-i+1)+f.b;
            val+=sB[i-1];
            if(val<dp[i].val)
            {
                dp[i].val=val;
                dp[i].r=f.p;
            }
            else if(val==dp[i].val)
                dp[i].r=max(dp[i].r,f.p);
        }
        dp[i].r++;
        dp[i].val+=cost;
        assert(aux==dp[i].val);
        while(!coada.empty())
        {
            int j=coada.back();
            if(dp[j].val>dp[i].val||(dp[j].val==dp[i].val&&dp[j].r<dp[i].r))
                coada.pop_back();
            else
                break;
        }
        coada.push_back(i);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    cin>>str;
    for(int i=0;i<str.size();i++)
    {
        if(str[i]=='A')
            A[++lga]=i+1;
        else
            B[++lgb]=i+1;
    }
    for(int i=1;i<=n;i++)
        if(A[i]>B[i])
        {
            ll x=A[i];
            A[i]=B[i];
            for(int j=i;j<=n;j++)
            {
                if(B[j]<x)
                {
                    B[j]++;
                    makegood++;
                }
                else
                    break;
            }
        }
    for(int i=1;i<=n;i++)
    {
        ll st=1;
        ll dr=n;
        ll cnt=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(B[mij]>A[i])
            {
                cnt=n-mij+1;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        Bspate[i]=cnt;
        st=1;
        dr=n;
        cnt=0;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(A[mij]<B[i])
            {
                cnt=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        Afata[i]=cnt;
        ll nxt=n+1;
        st=1;
        dr=n;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(A[mij]>B[i])
            {
                nxt=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        sB[i]=sB[i-1]+nxt;
    }
    A[n+1]=INF;
    Bspate[n+1]=0;
    Afata[n+1]=n;
    ll st=0;
    ll dr=2e12;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        solve(mij);
        if(dp[1].l<=k&&dp[1].r>=k)
        {
            ll rez=dp[1].val-mij*k;
            cout<<rez+makegood;
            return 0;
        }
        if(dp[1].l>k)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'void addL(func)':
chorus.cpp:78:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   78 |         bool ok=0;
      |              ^~
chorus.cpp: In function 'void solve(ll)':
chorus.cpp:165:14: warning: variable 'dbg' set but not used [-Wunused-but-set-variable]
  165 |         bool dbg=0;
      |              ^~~
chorus.cpp: In function 'int main()':
chorus.cpp:270:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  270 |     for(int i=0;i<str.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 26 / 26
• Subtask 5: 0 / 13