Submission #1180049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180049		user736482	Rope (JOI17_rope)	C++20	15 / 100	12 ms	5976 KiB

rope

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,k,m;
vector<ll>v2;
ll cnt[1000007];
ll ans[1000007];
vector<pair<ll,ll>>licz;
vector<pair<ll,ll>>v;//kolor,ile
map<pair<ll,ll>,vector<pair<pair<ll,ll>,pair<ll,bool>>>>mp;//para mniejszy wiekszy -> pocz,kon(pocz2-1),kon2,czymniejszyprzed

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    m++;
    cin>>a;
    v2.pb(a);
    cnt[a]++;
    for(ll i=1;i<n;i++){
        cin>>a;
        cnt[a]++;
        if(a==v2.back()){
        c++;
        v2.pb(a);}
        else{
            v.pb({v2.back(),c});
            c=1;
            v2.pb(a);
        }
    }
    v.pb({v2.back(),c});
    ll sm=0;
    for(ll i=1;i<v.size();i++){
       auto pom1=v[i-1],pom2=v[i];
       mp[{min(pom1.ff,pom2.ff),max(pom1.ff,pom2.ff)}].pb({{sm,sm+pom1.ss},{sm+pom1.ss+pom2.ss,pom1.ff<pom2.ff}});
       sm+=pom1.ss;
    }
    for(ll i=1;i<=m;i++){
        licz.pb({cnt[i],i});
        ans[i]=INFL;
    }
    sort(licz.begin(),licz.end());
    reverse(licz.begin(),licz.end());
    for(ll i=1;i<=m;i++){
        for(ll j=0;j<=m;j++){
            if(licz[j].ss==i)continue;
            if(mp[{min(i,licz[j].ss),max(i,licz[j].ss)}].empty()){
                ans[i]=min(ans[i],n-cnt[i]-licz[j].ff);
            //    cout<<i<<": "<<ans[i]<<"\n";
                break;
            }
            else{
                auto pom=mp[{min(i,licz[j].ss),max(i,licz[j].ss)}];
                sort(pom.begin(),pom.end());
                ll iledod=0;
                ll koszt[2];
                koszt[pom[0].ff.ss%2]=0;
                koszt[(pom[0].ff.ss+1)%2]=1;
                for(ll k=1;k<pom.size();k++){
                   // cout<<i<<": "<<koszt[0]<<" "<<koszt[1]<<"\n";
                    ll pom1=min(koszt[pom[k].ff.ss%2],koszt[(pom[k].ff.ss+1)%2]+1);
                    koszt[(pom[k].ff.ss+1)%2]=min(koszt[(pom[k].ff.ss+1)%2]+1,koszt[(pom[k].ff.ss)%2]+2);
                    koszt[pom[k].ff.ss%2]=pom1;
                }
                ans[i]=min(ans[i],n-cnt[i]-licz[j].ff+min(koszt[0],koszt[1]));
            }
        }
    }
    for(ll i=1;i<m;i++)cout<<ans[i]<<"\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20