Submission #1185570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185570		hamzabc	Ancient Books (IOI17_books)	C++20	50 / 100	160 ms	41280 KiB

books

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


using namespace std;

#define all(x) x.begin(), x.end()


vector<int> dsu;
vector<int> l;
vector<int> r;
vector<int> il;
vector<int> ir;
vector<int> used;
vector<array<int, 4>> araliklar, araliklar2;


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();
	long long int ret = 0;
	dsu.resize(n);
	l.resize(n);
	r.resize(n);
	il.resize(n, INT_MIN);
	ir.resize(n, INT_MAX);
	used.resize(n);
	for (int i = 0; i < n; i++){
		dsu[i] = i;
		l[i] = i;
		r[i] = i;
		if (i <= s)
			il[i] = i;
		if (i >= s)
			ir[i] = i;
	}
	for (int i = 0; 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)]);
			ir[goDSU(p[i])] = min(ir[goDSU(p[i])], ir[goDSU(i)]);
			l[goDSU(p[i])] = min(l[goDSU(p[i])], l[goDSU(i)]);
			il[goDSU(p[i])] = max(il[goDSU(p[i])], il[goDSU(i)]);
			dsu[goDSU(i)] = goDSU(p[i]);
		}
	}
	for (int i = 0; i < n; i++){
		if (!used[goDSU(i)] && l[goDSU(i)] != r[goDSU(i)]){
			used[goDSU(i)] = true;
			araliklar.push_back({ l[goDSU(i)], r[goDSU(i)], il[goDSU(i)], ir[goDSU(i)] });
		}
	}
	if (araliklar.size() == 0){
		return 0;
	}
	int mxr = araliklar[0][1];
	for (int i = 1; i < araliklar.size(); i++){
		int d = goDSU(araliklar[i][0]);
		if ((ir[goDSU(mxr)] == INT_MAX && araliklar[i][0] < mxr) || (il[goDSU(mxr)] == INT_MIN && araliklar[i][0] < mxr) || araliklar[i][0] < il[goDSU(mxr)] || (araliklar[i][1] > ir[goDSU(mxr)] && araliklar[i][0] < mxr)){
			r[goDSU(mxr)] = max(r[goDSU(mxr)], r[d]);
			ir[goDSU(mxr)] = min(ir[goDSU(mxr)], ir[d]);
			l[goDSU(mxr)] = min(l[goDSU(mxr)], l[d]);
			il[goDSU(mxr)] = max(il[goDSU(mxr)], il[d]);
			dsu[d] = goDSU(mxr);
		}
		mxr = max(mxr, araliklar[i][1]);
	}
	araliklar.clear();
	for (int i = 0; i < n; i++){
		used[goDSU(i)] = false;
	}
	int jl = -1, jr = 0;
	for (int i = 0; i < n; i++){
		if (i == s && p[s] == s){
			araliklar.push_back({ s, s, s, s });
			araliklar2.push_back({ s, s, s, s });
		}
		if (!used[goDSU(i)] && l[goDSU(i)] != r[goDSU(i)]){
			used[goDSU(i)] = true;
			araliklar.push_back({ l[goDSU(i)], r[goDSU(i)], il[goDSU(i)], ir[goDSU(i)] });
			araliklar2.push_back({ r[goDSU(i)], l[goDSU(i)], ir[goDSU(i)], il[goDSU(i)] });
		}
	}
	jl = lower_bound(all(araliklar), array<int, 4>{ l[goDSU(s)], -1, -1, -1 }) - araliklar.begin();
	jr = lower_bound(all(araliklar2), array<int, 4>{ r[goDSU(s)], -1, -1, -1 }) - araliklar2.begin();
	while (jr < araliklar2.size() - 1 || jl > 0){
		long long sum = 0, sum2 = 0;
		while (jr < araliklar2.size() - 1){
			sum += araliklar2[jr + 1][2] - araliklar2[jr][0];
			jr++;
			if (jr != araliklar2.size() && araliklar2[jr][1] < s){
				break;
			}
		}
		while (jl > 0){
			sum2 += araliklar[jl][2] - araliklar[jl - 1][0];
			jl--;
			if (araliklar[jl][1] > s){
				break;
			}
		}
		if (jr != araliklar2.size() && araliklar2[jr][1] < s){
			ret += min(sum, sum2) * 2;
			sum = 0;
			sum2 = 0;
		}else{
			ret += (sum + sum2) * 2;
		}
	}
	return ret;
}

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