제출 #410421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410421		Antekb	Ancient Books (IOI17_books)	C++14	100 / 100	392 ms	31048 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20);
int tab[N+N];
const int INF=1e9;
void ust(int l, int r, int m){
	r++;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1){
			tab[l]=min(tab[l], m);
			l++;
		}
		if(r&1){
			--r;
			tab[r]=min(tab[r], m);
		}
	}
}
int quer(int id){
	int ans=INF;
	for(id+=N; id>0; id>>=1){
		ans=min(ans, tab[id]);
	}
	return ans;
}
long long minimum_walk(std::vector<int> p, int s) {
	int n=p.size();
	/*s=n-s-1;
	for(int i=0; i<n; i++){
		p[i]=n-p[i]-1;
	}
	reverse(p.begin(), p.end());*/
	long long ans=0;
	for(int i=0; i<n; i++){
		ans+=abs(i-p[i]);
	}
	vector<int> V(n), col(n);
	int sum=0;
	for(int i=0; i<n; i++){
		sum-=V[i];
		sum-=V[p[i]];
		V[i]^=1;
		V[p[i]]^=1;
		sum+=V[i];
		sum+=V[p[i]];
		if(sum)col[i]=1;
	}
	bool czy=0;
	for(int i=0; i<s; i++){
		if(col[i])czy=1;
		if(czy && !col[i])ans+=2;
	}
	czy=0;
	for(int i=n-1; i>=s; i--){
		if(col[i])czy=1;
		if(czy && !col[i])ans+=2;
	}
	for(int i=1; i<N+N; i++){
		tab[i]=INF;
	}
	ust(s, s, 0);
	int l=s, r=s;
	while(l>=0 || r<n){
		if(l<0 || quer(l)>quer(r)){
			if(r<n-1)ust(r+1, r+1, quer(r)+1);
			ust(min(r, p[r]), max(r, p[r]), quer(r));
			r++;
		}
		else{
			if(l)ust(l-1, l-1, quer(l)+1);
			ust(min(l, p[l]), max(l, p[l]), quer(l));
			l--;
		}
	}
	int k=0;
	for(int i=0; i<n; i++){
		if((s-i)*(long long)(s-p[i])<0){
			k=max(k, quer(i));
		}
	}
	ans+=2*k;
	return ans;
}

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