Submission #68011

#	Time	Username	Problem	Language	Result	Execution time	Memory
68011		KLPP	Ancient Books (IOI17_books)	C++14	50 / 100	1649 ms	266724 KiB

books

#include "books.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long lld;
int arr[1000000];
int n;
int maxa,maxb;
int STm[1000000][32];
int STM[1000000][32];
int minimo(int i, int j){
	int size=j-i+1;
	int ans=10000000;
	int x=0;
	for(;(1<<(x+1))<=size;x++){
	}
	return min(STm[i][x],STm[j-(1<<x)+1][x]);
}
int maximo(int i, int j){
	int size=j-i+1;
	int ans=10000000;
	int x=0;
	for(;(1<<(x+1))<=size;x++){
	}
	return max(STM[i][x],STM[j-(1<<x)+1][x]);
}
lld computevalue(int i, int j){
    	//cout<<i<<" "<<j<<endl;
    	if(i<=maxa && maxb<=j)return 0;
    	int start=i;
    	int end=j;
    	int newstart=start;
    	int newend=end;
    	do{
    		//cout<<start<<" "<<end<<endl;
    		start=newstart;
    		end=newend;
    		newstart=min(start,minimo(start,end));
		newend=max(end,maximo(start,end));
    	}while(!(newstart==start && newend==end));
    	if(start>maxa){
    		return computevalue(start-1,end)+2;
    	}
    	else if(end<maxb){
    		return computevalue(start,end+1)+2;
    	}
    	return 0;
}
lld abs(lld x){
    	if(x>0)return x;
    	return -x;
}
long long minimum_walk(std::vector<int> p, int s) {
    	n=p.size();
    	for(int i=0;i<n;i++){
    		arr[i]=p[i];
    	}
    	maxa=n;
    	for(int i=0;i<n;i++){
    		if(p[i]!=i){
    			maxa=i;
    			i=n;
    		}
    	}
    	maxb=-1;
    	for(int i=n-1;i>-1;i--){
    		if(p[i]!=i){
    			maxb=i;
    			i=-1;
    		}
    	}
	for(int i=0;i<n;i++){
		STm[i][0]=arr[i];
		STM[i][0]=arr[i];
	}
	for(int j=1;j<32;j++){
		for(int i=0;i<n;i++){
			STm[i][j]=min(STm[i][j-1],STm[min(i+(1<<(j-1)),n-1)][j-1]);
			STM[i][j]=max(STM[i][j-1],STM[min(i+(1<<(j-1)),n-1)][j-1]);
			//cout<<STm[i][j]<<" "<<STM[i][j]<<endl;
		}
	}
	
	lld ans=0;
    	for(int i=0;i<n;i++)ans+=abs(p[i]-i);
    	//cout<<ans<<endl;
    	ans+=computevalue(s,s);
    	return ans;
}

Compilation message (stderr)

books.cpp: In function 'int minimo(int, int)':
books.cpp:14:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=10000000;
      ^~~
books.cpp: In function 'int maximo(int, int)':
books.cpp:22:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans=10000000;
      ^~~

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