제출 #390729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390729		alireza_kaviani	고대 책들 (IOI17_books)	C++11	100 / 100	489 ms	92228 KiB

books

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

typedef long long ll;
typedef pair<int, int> pii;

#define sep			' '
#define X			first
#define Y			second
#define all(x)		(x).begin() , (x).end()
#define SZ(x)		int(x.size())

const int MAXN = 1e6 + 10;

int n , mark[MAXN] , mx[MAXN] , mn[MAXN] , par[MAXN] , sz[MAXN];
ll ans , ps[MAXN];
vector<int> comp[MAXN];

int Find(int v){
	return (par[v] == -1 ? v : par[v] = Find(par[v]));
}

void Union(int v , int u){
	v = Find(v); u = Find(u);
	if(v == u)	return;
	if(sz[v] < sz[u])	swap(v , u);
	par[u] = v;
	sz[v] += sz[u];
	mx[v] = max(mx[v] , mx[u]);
	mn[v] = min(mn[v] , mn[u]);
}

int count(int l , int r , int x){
	int ans = 0;
	for(int i = l ; i < r ; i++){
		ans += (ps[i] == x);
	}
	return ans;
}

ll minimum_walk(vector<int> p, int s) {
	fill(mx , mx + MAXN , -1);
	fill(mn , mn + MAXN , MAXN);
	fill(par , par + MAXN , -1);
	fill(sz , sz + MAXN , 1);
	n = p.size();
	vector<pii> vec;
	for(int i = 0 ; i < n ; i++){
		ans += abs(i - p[i]);
		if(mark[i])	continue;
		int x = i , flag = 0;
		vector<int> v;
		while(!mark[x]){
			mark[x] = 1; mn[x] = mx[x] = x;
			v.push_back(x);
			x = p[x];
		}
		sort(all(v));
		for(int j = 0 ; j + 1 < SZ(v) ; j++){
			Union(v[j] , v[j + 1]);
			vec.push_back({v[j] , v[j + 1]});
		}
	}
	vector<int> stk;
	sort(all(vec));
	for(int i = 0 ; i < SZ(vec) ; i++){
		while(SZ(stk) > 0 && vec[i].Y > vec[stk.back()].Y){
			if(vec[i].X < vec[stk.back()].Y)	Union(vec[i].X , vec[stk.back()].X);
			stk.pop_back();
		}
		stk.push_back(i);
	}
	vector<int> v;
	for(int i = 0 ; i < n ; i++){
		comp[Find(i)].push_back(i);
		if(Find(i) == i){
			ps[mn[i]]++; ps[mx[i]]--;
			if(mn[i] <= s && s <= mx[i]){
				v.push_back(i);
			}
		}
	}
	partial_sum(ps , ps + MAXN , ps);
	int l = 0 , r = n;
	while(l < s && ps[l] == 0)	l++;
	while(s <= r && ps[r] == 0)	r--;
	ans += 2 * count(l , r + 1 , 0);
	for(int i = 0 ; i + 1 < SZ(v) ; i++){
		int l2 = mn[v[i + 1]] , r2 = mx[v[i + 1]];
		int l1 = (*prev(lower_bound(all(comp[v[i]]) , l2)));
		int r1 = (*lower_bound(all(comp[v[i]]) , r2));
//		cout << l1 << sep << l2 << sep << r1 << sep << r2 << endl;
		ans += min(count(l1 , l2 , i + 1) , count(r2 , r1 , i + 1)) * 2;
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:52:15: warning: unused variable 'flag' [-Wunused-variable]
   52 |   int x = i , flag = 0;
      |               ^~~~

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