Submission #1185019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185019		hamzabc	Ancient Books (IOI17_books)	C++20	50 / 100	124 ms	32200 KiB

books

#include "books.h"
#include <bits/stdc++.h>


using namespace std;


vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> used;
vector<pair<int, int>> araliklar;


int goDSU(int a){
	if (dsu[a] == a)
		return a;
	dsu[a] = goDSU(dsu[a]);
	return dsu[a];
}


long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	dsu.resize(n);
	l.resize(n);
	r.resize(n);
	used.resize(n);
	for (int i = 0; i < n; i++){
		p[i];
		dsu[i] = i;
		l[i] = i;
		r[i] = i;
	}
	int L = 0;
	for (; n > 0; n--){
		if (p[n - 1] != n - 1)
			break;
	}
	if (n == 0)
		return 0;
	for (; L < n; L++){
		if (p[L] != L)
			break;
	}
	long long int ret = 0;
	for (int i = L; i < n; i++){
		ret += abs(p[i] - i);
		if (goDSU(i) != goDSU(p[i])){
			r[goDSU(p[i])] = max(r[goDSU(p[i])], r[goDSU(i)]);
			l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
			dsu[goDSU(i)] = goDSU(p[i]);
		}
	}
	for (int i = L; i < n; i++){
		if (!used[goDSU(i)]){
			used[goDSU(i)] = true;
			araliklar.push_back({ l[goDSU(i)], r[goDSU(i)] });
		}
	}
	sort(araliklar.begin(), araliklar.end());
	int mxr = araliklar[0].second;
	for (int i = 1; i < araliklar.size(); i++){
		if (mxr > araliklar[i].first){
			mxr = max(mxr, araliklar[i].second);
		}else{
			mxr = max(mxr, araliklar[i].second);
			ret += 2;
		}
	}
	return ret + max(0, L - s) * 2 + max(0, s - n) * 2;
}

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