Submission #137718

#	Time	Username	Problem	Language	Result	Execution time	Memory
137718		ckodser	Ancient Books (IOI17_books)	C++14	70 / 100	242 ms	31568 KiB

books

#include "books.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e6+500;
const ll inf=1e9+900;

vector<ll> p;
bool vis[maxn];
ll d[maxn];

ll last=-1,fir,N;
ll cnt=0;
ll mxx[maxn];
ll mnn[maxn];

const ll maxm=1050;

bool visdp[maxm][maxm];
ll dpp[maxm][maxm];

ll findmnn[maxm][maxm];
ll findmxx[maxm][maxm];

ll findDp(ll l,ll r){
    l=max(l,0);
    r=min(r,N-1);
    if(l<=fir && last<=r)return 0;
    if(visdp[l][r])return dpp[l][r];
    visdp[l][r]=1;
    dpp[l][r]=inf;
    if(findmnn[l][r]<l){
	dpp[l][r]=findDp(findmnn[l][r],r);
    }else if(findmxx[l][r]>r){
	dpp[l][r]=findDp(l,findmxx[l][r]);
    }else{
	dpp[l][r]=min(findDp(l,r+1)+2,findDp(l-1,r)+2);
    }
    return dpp[l][r];
}



void dfs(ll a){
    if(vis[a])return;
    vis[a]=2;
    d[a]=cnt;
    dfs(p[a]);
}
long long minimum_walk(vector<int> P, int s){
    p=P;
    ll n=p.size();
    N=n;
    long long ans=0;
    for(ll i=0;i<n;i++){
	if(!vis[i]){
	    dfs(i);
	    cnt++;
	}
	if(p[i]!=i)last=i;
	ans+=abs(i-p[i]);
    }
    for(ll i=n-1;i>=0;i--){
	if(p[i]!=i){
	    fir=i;
	}
    }
    if(last==-1)return 0;
    fill(mnn,mnn+maxn,inf);
    fill(mxx,mxx+maxn,0);

    for(ll i=0;i<n;i++){
	mnn[d[i]]=min(mnn[d[i]],i);
	mxx[d[i]]=max(mxx[d[i]],i);
    }
    if(s<=fir){
	ll t=s;
	for(ll i=s;i<=last;i++){
	    if(t<i){
		ans+=2;
		t=max(t,i);
	    }
	    t=max(t,mxx[d[i]]);
	}
	return ans;
    }
    if(s>=last){
   	ll t=s;
	for(ll i=s;i>=fir;i--){
	    if(i<t){
		ans+=2;
		t=min(t,i);
	    }
	    t=min(t,mnn[d[i]]);
	}
	return ans;
    }
    if(n<=1000){
	for(ll t=1;t<=n;t++){
	    for(ll l=0;l+t-1<n;l++){
		ll r=l+t-1;
		if(t==1){
		    findmnn[l][r]=mnn[d[l]];
		    findmxx[l][r]=mxx[d[l]];
		}else{
		    findmnn[l][r]=min(findmnn[l][r-1],mnn[d[r]]);
		    findmxx[l][r]=max(findmxx[l][r-1],mxx[d[r]]);
		}
	    }
	}
	return findDp(mnn[d[s]],mxx[d[s]])+ans;
    }
    


    return ans;
}

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