Submission #1012229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012229		hyakup	Ancient Books (IOI17_books)	C++17	0 / 100	364 ms	1048576 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
#define ll long long
#pragma GCC optimize("O3")

const ll maxn = 1e6 + 10;

bool marc[maxn], especial[maxn];
queue<int> seg[4*maxn];

queue<int> fila;
void update( int pos, int ini, int fim, int ki, int kf ){
	if( ki > fim || ini > kf ) return;
	if( ki <= ini && fim <= kf ){ seg[pos].push(ki); return; }
	int mid = (ini + fim)/2;
	update( 2*pos, ini, mid, ki, kf ); update( 2*pos + 1, mid + 1, fim, ki, kf );
}

void activate( int pos, int ini, int fim, int id ){
	while( !seg[pos].empty() ){
		if( !marc[seg[pos].front()] ){
			marc[seg[pos].front()] = true;
			fila.push(seg[pos].front());
		}
		seg[pos].pop();
	}
	if( ini == fim ) return;
	int mid = (ini + fim)/2;
	if( id <= mid ) activate( 2*pos, ini, mid, id );
	else activate( 2*pos + 1, mid + 1, fim, id );
}

long long minimum_walk(vector<int> p, int s) {
	if( is_sorted( p.begin(), p.end() ) ) return 0;
	ll n = (ll)p.size();
	ll resp = 0;
	for( ll i = 0; i < (ll)p.size(); i++ ) resp += (ll)abs(p[i] - i);
	int maxi = -1;
	bool contido = false;
	for( ll i = 0; i < n; i++ ) if( !marc[i] && p[i] != i ){
		if( i > maxi ){
			if( maxi != -1 ) resp += 2LL*(i - maxi);
			fila.push(i);
		}
		int cur = p[i], maior = i;
		while( cur != i ){
			maxi = max( maxi, cur );
			maior = max( maior, cur );
			cur = p[cur];
		}
		update( 1, 0, n - 1, i, maior );
		if( i <= s && s <= maxi ) contido = true;
	}

	while( !fila.empty() ){
		int cur = fila.front(); fila.pop();
		marc[cur] = true;
		while( !especial[cur] ){
			especial[cur] = true;
			activate( 1, 0, n - 1, cur );
			cur = p[cur];
		}
	}


	ll l = s, r = s;
	while( l >= 0 && !especial[l] ) l--;
	while( r < n && !especial[r] ) r++;
	if( contido ) resp += 2LL*min( s - l, r - s );
	else{
		if( l == -1 ) resp += 2LL*(r - s);
		else if( r == n ) resp += 2LL*(s - l);
	}
	return resp;
}

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