Submission #1262363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262363		PlayVoltz	Ancient Books (IOI17_books)	C++20	100 / 100	190 ms	31868 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> l, r;

void extend(int &cl, int &cr){
	int mx=max(r[cr], r[cl]), mn=min(l[cr], l[cl]);
	while (cl>mn||cr<mx){
		while (cl>mn){
			--cl;
			mn=min(mn, l[cl]);
			mx=max(mx, r[cl]);
		}
		while (cr<mx){
			++cr;
			mn=min(mn, l[cr]);
			mx=max(mx, r[cr]);
		}
	}
}

long long minimum_walk(vector<signed> P, signed S) {
	int s=S, low=s, high=s;
	vector<int> p(P.size());
	l.assign(p.size(), 0);
	r.assign(p.size(), 0);
	for (int i=0; i<p.size(); ++i)p[i]=P[i];
	vector<bool> visited(p.size(), 0);
	int res=0;
	for (int i=0; i<p.size(); ++i){
		if (p[i]==i){
			l[i]=r[i]=i;
			continue;
		}
		high=max(high, i);
		low=min(low, i);
		if (visited[i])continue;
		int c=p[i], mx=i;
		visited[i]=1;
		l[i]=i;
		res+=abs(i-p[i]);
		while (c!=i){
			l[c]=i;
			mx=max(mx, c);
			visited[c]=1;
			res+=abs(c-p[c]);
			c=p[c];
		}
		c=p[i];
		r[i]=mx;
		while (c!=i){
			r[c]=mx;
			visited[c]=1;
			c=p[c];
		}
	}
	int cl=s, cr=s;
	while (low<cl||high>cr){
		extend(cl, cr);
		int al=cl, ar=cr, bl=cl, br=cr, a=0, b=0;
		while (al>low&&ar==cr){
			--al;
			a+=2;
			extend(al, ar);
		}
		while (br<high&&bl==cl){
			++br;
			b+=2;
			extend(bl, br);
		}
		if (ar!=cr)res+=min(a, b);
		else res+=a+b;
		cl=al, cr=br;
	}
	return res;
}

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