Submission #971242

#	Time	Username	Problem	Language	Result	Execution time	Memory
971242		MilosMilutinovic	Ancient Books (IOI17_books)	C++14	42 / 100	350 ms	200324 KiB

books

#include "books.h"
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

bool was[1000005];
int n,sl[1000005],sr[1000005],rt[100005];

namespace rmq{
	int mina[1000005][22],maxa[1000005][22],logs[1000005]; 
	void build(){
		for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
		for(int i=0;i<n;i++){
			mina[i][0]=sl[rt[i]];
			maxa[i][0]=sr[rt[i]];
		}
		for(int j=1;j<22;j++){
			for(int i=0;i+(1<<j)<=n;i++){
				mina[i][j]=min(mina[i][j-1],mina[i+(1<<(j-1))][j-1]);
				maxa[i][j]=max(maxa[i][j-1],maxa[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int qmin(int l,int r){
		int k=logs[r-l+1];
		return min(mina[l][k],mina[r-(1<<k)+1][k]);
	}
	int qmax(int l,int r){
		int k=logs[r-l+1];
		return max(maxa[l][k],maxa[r-(1<<k)+1][k]);
	}
};

void work(int&l,int&r){
	while(true){
		int fl=rmq::qmin(l,r);
		int fr=rmq::qmax(l,r);
		if(fl==l&&fr==r) break;
		l=fl; r=fr;
	}
}

ll minimum_walk(vector<int> p,int s){
	n=(int)p.size();
	ll ans=0;
	for(int i=0;i<n;i++) ans+=abs(p[i]-i);
	for(int i=0;i<n;i++){
		if(was[i]) continue;
		sl[i]=i; sr[i]=i;
		rt[i]=i;
		int x=i;
		while(!was[x]){
			chkmin(sl[i],x);
			chkmax(sr[i],x);
			rt[x]=i;
			was[x]=true;
			x=p[x];
		}
	}
	rmq::build();
	int L=s,R=s;
	for(int i=0;i<n;i++){
		if(p[i]==i) continue;
		chkmin(L,i); chkmax(R,i);
	}
	int cl=s,cr=s;
	while(cl>L||cr<R){
		work(cl,cr);
		int nl=cl,nr=cr;
		int pl=cl,pr=cr;
		ll a=0;
		bool lt=false;
		while(pl>L&&pr==cr){
			a+=2;
			pl--;
			work(pl,pr);
		}
		chkmin(nl,pl);
		chkmax(nr,pr);
		if(pr>cr) lt=true;
		pl=cl; pr=cr;
		ll b=0;
		bool rt=false;
		while(pl==cl&&pr<R){
			b+=2;
			pr++;
			work(pl,pr);
		}
		chkmin(nl,pl);
		chkmax(nr,pr);
		if(pl<cl) rt=true;
		if(lt&&rt) ans+=min(a,b);
		else ans+=a+b;
		cl=nl; cr=nr;
	}
	return ans;
}

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