Submission #1178819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178819		ace5	Chorus (JOI23_chorus)	C++20	16 / 100	0 ms	544 KiB

chorus

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 2e9;
const int maxn = int(1e6)+5;


struct line
{
    line(ll _r,ll _b,int _cnt){r = _r;b = _b;cnt = _cnt;};
    line(){};
    ll r,b;
    int cnt;
    ll operator ()(ll x){return r * x + b;};
};

ll inter(line a,line b)
{
    //assert(a.r != b.r);
    if((b.b-a.b)%(a.r-b.r) == 0)
    {
        return (a.cnt <= b.cnt ? (b.b-a.b)/(a.r-b.r) : (b.b-a.b)/(a.r-b.r)-1);
    }
    else
    {
        return (b.b-a.b)/(a.r-b.r);
    }
}

vector<pair<int,int>> pr;
vector<line> cl;
int tind = 0;
int ca[maxn];
ll one_seg[maxn];
ll lseg[maxn];
line lines[maxn];

void add(line l)
{
    //cout << "newline " << l.r << ' ' << l.b << endl;
  //  cout << "!" << endl;
    while(pr.size() && inter(cl.back(),l) < pr.back().first)
    {
        pr.pop_back();
        cl.pop_back();
    }
   // cout << "!2" << endl;
    if(!pr.size())
    {
        pr.push_back({-INF,INF});
        cl.push_back(l);
    }
    else
    {
        int t = inter(cl.back(),l);
        pr.back().second = t;
        pr.push_back({t+1,INF});
        cl.push_back(l);
    }
   // cout << "!2" << endl;
}

int get(int x)
{
    if(cl.size() == 0)
        return -1;
    if(cl.back()(x) < cl[tind](x))
    {
        tind = cl.size()-1;
    }
    while(tind+1 < cl.size() && pr[tind+1].first <= x)
    {
        tind++;
    }
    return tind;
}

pair<ll,int> check(ll lm,int n)
{
    pr.clear();
    cl.clear();
    tind = 0;
    pair<ll,int> dp[n];
    //cout << "!" << endl;
    for(int j = n-1;j >= 0;--j)
    {
       // cout << j << endl;
        int u = get(-j);
        //cout << j << endl;
        if(u == -1)
            dp[j] = {one_seg[j] + lm,1};
        else
        {
           // cout << cl[u].r << ' ' << cl[u].b << ' ' << cl[u].cnt << endl;  
            dp[j] = min(make_pair(one_seg[j] + lm,1),make_pair(cl[u](-j)+lm+ca[j]*j-lseg[j],cl[u].cnt+1));
        }
            //cout << j << endl;
       // cout << lines[j].r << ' ' << lines[j].b << endl;
        add(line(lines[j].r,lines[j].b + dp[j].first,dp[j].second));
       // cout << "! " << dp[j].first << ' ' << dp[j].second << endl;
    }
  //  cout << dp[0].first << "\n";
    return dp[0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    ll base_op = 0;
    //do s psp
    vector<int> apos,bpos;
    for(int i = 0;i < 2*n;++i)
    {
        if(s[i] == 'A')
            apos.push_back(i);
        else
            bpos.push_back(i);
    }
    string t;
    int pnta = 0;
    int cbal = 0;
    int ac = 0;
    for(int i = 0;i < s.size();++i)
    {
        if(s[i] == 'A')
        {
            ac++;
            if(pnta < n && apos[pnta] == i)
            {
                pnta++;
                cbal ++;
                t += 'A';
            }
        }
        else
        {
            if(cbal > 0)
            {
                cbal--;
                t += 'B';
            }
            else
            {
               // cout << i << ' ' << apos[pnta]-i+ac-pnta << endl;
                base_op += apos[pnta]-i+ac-pnta;
                pnta++;
                t += 'A';
                t += 'B';
            }
        }
    }
   // cout << base_op << endl;
    s = t;
    //count one_seg
    int pnt = n-1;
    pnta = 0;
    ll ans=  0;
    for(int j = 2*n-1;j >= 0;--j)
    {
        if(s[j] == 'B')
        {
            ans += pnta;
            one_seg[pnt--] = ans;
        }
        else
        {
            pnta++;
        }
    }
    //count lseg and lines
    pnt = 0;
    ans=  0;
    pnta = 0;
    for(int j = 0;j < 2*n;++j)
    {
        if(s[j] == 'B')
        {
            ca[pnt] = pnta; 
            lseg[pnt++] = ans;
        }
        else
        {
            lines[pnta++] = line(pnta,ans,0);
            ans += pnt;
        }
    }
   // cout << "!" << endl;
    ll l = 0,r = 1e18;
    while(l < r)
    {
        ll m = (l+r)/2;
       // cout << "? " << m << endl;
        if(check(m,n).second > k)
        {
            l = m+1;
        }
        else
            r = m;
    } 
   // cout << l << ' ';
    cout << check(l,n).first - k * l + base_op << endl;
    return 0;
}

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