Submission #307583

#	Time	Username	Problem	Language	Result	Execution time	Memory
307583		CaroLinda	Ancient Books (IOI17_books)	C++14	50 / 100	630 ms	26760 KiB

books

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

#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

using namespace std ;

long long minimum_walk(vector<int> p, int S) 
{

	assert( S == 0 ) ;

	int n = sz(p) ;
	long long ans = 0 ;
	int l , r ;

	for(l = 0 ; l < n ; l++ )
	{
		if(p[l] == l) ans += 2LL ;
		else break ;
	}

	if(l == n) return 0 ;

	for(r = n-1 ; r>= 0 ; r-- )
		if( p[r] != r ) break ;

	set<int> s ;
	s.insert( p[l] ) ;

	for(int i = l+1 ; i <= r ; i++ )
	{

		while( sz(s) )
		{
			auto it = s.begin() ;

			if( *it <= i-1 ) s.erase(it) ;
			else break ;
		}


		//Sobre a aresta i-1 -> i
		ans += max(2LL, 2LL*sz(s) ) ;
		s.insert( p[i] ) ;

	}

	return ans ;
}

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