Submission #790604

#	Time	Username	Problem	Language	Result	Execution time	Memory
790604		FEDIKUS	Ancient Books (IOI17_books)	C++17	100 / 100	135 ms	19956 KiB

books

#include "books.h"
#include<bits/stdc++.h>
 
using ll = long long;
using namespace std;
 
const int maxn=1e6+10;
 
int n;
bitset<maxn> bio;
int cale[maxn];
int mini[maxn];
int maxi[maxn];
int klk=0;
 
ll minimum_walk(vector<int> p, int s) {
	n=p.size();
	ll ret=0;
	int imal=n,imar=-1;
	for(int i=0;i<n;i++){
		if(p[i]!=i) imal=min(imal,i);
		if(p[i]!=i) imar=i;
		ret+=abs(p[i]-i);
		if(bio[i]) continue;
		int tren=i;
		mini[klk]=tren; maxi[klk]=tren;
		while(!bio[tren]){
			bio[tren]=true;
			cale[tren]=klk;
			mini[klk]=min(mini[klk],tren);
			maxi[klk]=max(maxi[klk],tren);
			tren=p[tren];
		}
		klk++;
	}
	imal=min(imal,s);
	imar=max(imar,s);
	int l=s,r=s;
	int tl=mini[cale[s]],tr=maxi[cale[s]];
	int dodaol=0,dodaor=0;
	while(l!=imal || r!=imar){
		bool pl=false,pr=false;
		if(l!=tl || r!=tr){
			if(l!=tl){
				l--;
				tl=min(tl,mini[cale[l]]);
				tr=max(tr,maxi[cale[l]]);
			}
			if(r!=tr){
				r++;
				tl=min(tl,mini[cale[r]]);
				tr=max(tr,maxi[cale[r]]);
			}
			continue;
		}

		while(l>imal && maxi[cale[l-1]]<=r){
			l--;
			if(l<tl){
				ret+=2;
				dodaol++;
			}
			tl=min(tl,mini[cale[l]]);
		}

		while(r<imar && mini[cale[r+1]]>=l){
			r++;
			if(r>tr){
				ret+=2;
				dodaor++;
			}
			tr=max(tr,maxi[cale[r]]);
		}

		if(l==imal && r==imar) break;
		
		ret-=2*max(dodaol-int(r>=tr),dodaor-int(l<=tl));
		l--;
		tl=min(tl,mini[cale[l]]);
		tr=max(tr,maxi[cale[l]]);
		dodaol=0;
		dodaor=0;
	}
	return ret;
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:42:8: warning: unused variable 'pl' [-Wunused-variable]
   42 |   bool pl=false,pr=false;
      |        ^~
books.cpp:42:17: warning: unused variable 'pr' [-Wunused-variable]
   42 |   bool pl=false,pr=false;
      |                 ^~

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