Submission #70922

#	Time	Username	Problem	Language	Result	Execution time	Memory
70922		gnoor	Ancient Books (IOI17_books)	C++17	50 / 100	316 ms	34152 KiB

books

#include "books.h"

#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

bool visit[1000100];
long long disl[1000100];
long long disr[1000100];

vector<pair<int,int>> uni(vector<pair<int,int>> &tbl) {
	sort(tbl.begin(),tbl.end(),[](const pair<int,int> &a,const pair<int,int> &b) {
			if (a.second!=b.second) return a.second<b.second;
			return a.first<b.first;
			});
	vector<pair<int,int>> re;
	for (int i=0;i<(int)tbl.size();i++) {
		int curl=tbl[i].first;
		while (!re.empty()&&tbl[i].first<=re.back().second) {
			curl=min(curl,re.back().first);
			re.pop_back();
		}
		re.push_back({curl,tbl[i].second});
	}
	return re;
}

struct seg {
	int cl,cr,pl,pr;
};

vector<seg> rem(vector<seg> &tbl,vector<seg> &out) {
	sort(tbl.begin(),tbl.end(),[](const seg &a, const seg &b) {
			if (a.pr!=b.pr) return a.pr<b.pr;
			return a.pl>b.pl;
			});
	
	vector<seg> res;
	for (int i=0;i<(int)tbl.size();i++) {
		while (!res.empty()&&tbl[i].pl<=res.back().pl) {
			out.push_back(res.back());
			res.pop_back();
		}
		res.push_back(tbl[i]);
	}
	return res;
}

long long minimum_walk(vector<int> p, int s) {
	int n=(int)p.size();
	vector<pair<int,int>> coord;

	vector<seg> over;
	vector<seg> nonover;

	long long ans=0;

	for (int i=0;i<n;i++) {
		if (visit[i]) continue;
		visit[i]=true;
		int mn=i;
		int mx=i;

		int cl=-1e9;
		int cr=1e9;
		if (i<=s) cl=max(cl,i);
		if (i>=s) cr=min(cr,i);

		int cur=p[i];
		ans+=abs(p[i]-i);
		while (cur!=i) {
			visit[cur]=true;
			mx=max(mx,cur);
			mn=min(mn,cur);

			if (cur<=s) cl=max(cl,cur);
			if (cur>=s) cr=min(cr,cur);

			ans+=abs(p[cur]-cur);
			cur=p[cur];
		}

		if (mn==mx) continue;

		coord.push_back({mn,mx});

		if (mn>=s||mx<=s) nonover.push_back(seg{cl,cr,mn,mx});
		else over.push_back(seg{cl,cr,mn,mx});
	}
	coord.push_back({s,s});
	auto re=uni(coord);
	for (int i=1;i<(int)re.size();i++) {
		ans+=(re[i].first-re[i-1].second)*2;
	}

	if (over.empty()) {
		return ans;
	}

	//-------------------------------------------

	over=rem(over,nonover);

	int tgtl=-1e9;
	int tgtr=1e9;
	for (auto &i:over) {
		tgtl=max(tgtl,i.cl);
		tgtr=min(tgtr,i.cr);
	}

	memset(disl,63,sizeof(disl));
	memset(disr,63,sizeof(disr));
	int curr,curl;

	//----------------------------

	long long addr=0;
	sort(nonover.begin(),nonover.end(),[](const seg &a, const seg &b) {
			return a.cr<b.cr;
			});

	curr=s;
	curl=s;
	for (int i=0;i<(int)nonover.size();i++) {
		if (nonover[i].cr==1e9) break;
		if (nonover[i].cr>curr) {
			addr+=(nonover[i].cr-curr)*2ll;
		}
		curr=max(curr,nonover[i].pr);
		curl=min(curl,nonover[i].pl);
		disl[curl]=min(disl[curl],addr);
	}
	for (int i=1;i<=s;i++) {
		disl[i]=min(disl[i],disl[i-1]);	
	}

	//----------------------------

	long long addl=0;
	sort(nonover.begin(),nonover.end(),[](const seg &a, const seg &b) {
			return a.cl>b.cl;
			});

	curr=s;
	curl=s;
	for (int i=0;i<(int)nonover.size();i++) {
		if (nonover[i].cl==-1e9) break;
		if (nonover[i].cl<curl) {
			addl+=(curl-nonover[i].cl)*2ll;
		}
		curl=min(curl,nonover[i].pl);
		curr=max(curr,nonover[i].pr);
		disr[curr]=min(disr[curr],addl);
	}
	for (int i=n-2;i>=s;i--) {
		disr[i]=min(disr[i],disr[i+1]);
	}

	//-------------------------
	
	addr=0;
	sort(nonover.begin(),nonover.end(),[](const seg &a, const seg &b) {
			return a.cr<b.cr;
			});

	curr=s;
	for (int i=0;i<(int)nonover.size()&&curr<tgtr;i++) {
		if (nonover[i].cr==1e9) break;
		if (nonover[i].cr>curr) {
			addr+=(nonover[i].cr-curr)*2ll;
		}
		curr=max(curr,nonover[i].pr);
		addr=min(addr,disr[curr]);
	}
	if (curr<tgtr) addr+=(tgtr-curr)*2ll;

	//--------------------

	addl=0;
	sort(nonover.begin(),nonover.end(),[](const seg &a, const seg &b) {
			return a.cl>b.cl;
			});

	curl=s;
	for (int i=0;i<(int)nonover.size()&&curl>tgtl;i++) {
		if (nonover[i].cl==-1e9) break;
		if (nonover[i].cl<curl) {
			addl+=(curl-nonover[i].cl)*2ll;
		}
		curl=min(curl,nonover[i].pl);
		addl=min(addl,disl[curl]);
	}
	if (curl>tgtl) addl+=(curl-tgtl)*2ll;

	//-------------------

	return ans+min(addl,addr);
}

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