Submission #307585

#	Time	Username	Problem	Language	Result	Execution time	Memory
307585		CaroLinda	Ancient Books (IOI17_books)	C++14	50 / 100	604 ms	19964 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) 
{

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

	while( l < n && p[l] == l ) l++ ;
	while( r > S && p[r] == r ) r-- ;

	if(l == n) return 0LL ;

	if( l > S ) ans += 2LL * ( l - S ) ;

	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