제출 #1202854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202854		YesterdayOnceMore	고대 책들 (IOI17_books)	C++20	70 / 100	2093 ms	19956 KiB

books

#include "books.h"

#include <cstdio>
#include <vector>
#include <cassert>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+6;
int id[N],lp[N],rp[N];
typedef vector<int> vi;
void extend(int &ll,int &rr,vi &c,vi &l,vi &r)
{
    int lp=min(l[c[ll]],l[c[rr]]),rp=max(r[c[ll]],r[c[rr]]);
    while(ll>lp||rr<rp)
    {
    //    cout<<lp<<'*'<<rp<<' '<<ll<<' '<<rr<<endl;
        if(ll>lp)
        {
            --ll;
            lp=min(lp,l[c[ll]]);
            rp=max(rp,r[c[ll]]);
        }else{
            ++rr;
            lp=min(lp,l[c[rr]]);
            rp=max(rp,r[c[rr]]);
        }
    }
}
LL go(int l,int r,int tl,int tr,vi &c,vi &lc,vi &rc)
{
    int ans=0;
    int nl,nr;
//    cout<<l<<' '<<r<<' '<<tl<<' '<<tr<<'\n';
    while(l>tl||r<tr)
    {
        extend(l,r,c,lc,rc);
    //    cout<<l<<' '<<r<<endl;
        int ll=l,rl=l,ansl=0,nextl=0;
        while(1)
        {
            if(ll<=tl)
            {
                break;
            }
            ll--;ansl+=2;
            extend(ll,rl,c,lc,rc);
            if(rl>r)
            {
                nextl=1;
                break;
            }
        }
    //    cout<<ll<<' '<<rl<<" l\n";
        int lr=r,rr=r,ansr=0,nextr=0;
        while(1)
        {
            if(rr>=tr)
            {
                break;
            }
            rr++;ansr+=2;
            extend(lr,rr,c,lc,rc);
            if(lr<l)
            {
                nextr=1;
                break;
            }
        }
    //    cout<<lr<<' '<<rr<<" r\n";
        assert(!(nextl^nextr));
        if(nextl&&nextr)
        {
            ans+=min(ansl,ansr);
        }else{
            ans+=ansl+ansr;
        }
        l=min(ll,lr);
        r=max(rl,rr);
    }
    return ans;
}
long long minimum_walk(std::vector<int> p, int s) {
    //essential edges
    LL ans=0;
    int n=p.size();
    vector<int>c(n),l(n),r(n);
    int tot=0,L=s,R=s;
    for(int i=0;i<n;i++)
    {
        ans+=abs(i-p[i]);
        if(c[i]==0)
        {
            ++tot;
            l[tot]=i;r[tot]=i;c[i]=tot;
            for(int x=p[i];x!=i;x=p[x])
            {
                c[x]=tot;r[tot]=max(r[tot],x);
            }
        if(i!=p[i])
        {
            L=min(L,l[tot]);
            R=max(R,r[tot]);
        }
        }
    }
//    cout<<ans<<'\n';
	return ans+go(s,s,L,R,c,l,r);
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 0 / 30