Submission #309832

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
309832	2020-10-04T16:19:36 Z	CaroLinda	Ancient Books (IOI17_books)	C++14	Compilation error	0 ms	0 KB

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())
 
const int MAX = 1e6+10 ;
 
using namespace std ;
 
//Tentando uma ideia (provavelmente vai dar errado mas vamos nessa)
 
int bit[MAX] ;
void upd(int pos, int val)
{
	if(pos == 0 ) return ;
 
	for(int i = pos ; i < MAX ; i += (i&-i) )
		bit[i] = max(bit[i] , val) ;
}
int qry(int pos)
{
	if(pos == 0) return -1 ;
 
	int tot = -1 ;
	for(int i = pos ; i > 0 ; i -= (i&-i) )
		tot = max(tot, bit[i]);
	return tot ;
}
 
 
long long minimum_walk(vector<int> p, int s) 
{
 
	int n = sz(p) ;
	ll ans = 0LL ;
 
	lp(i,0,n) ans += (ll)(abs(p[i]-i)) ;
 
	int L = 0  ;
	int R = n-1 ;
 
	while(L < s && p[L] == L ) L++ ;
	while(R > s && p[R] == R) R-- ;
 
	vector<bool> vis( n, false ) ;
	vector<pii> intervalo(n, make_pair(-1,-1) ) ;
 
	for(int i = L ; i <= R ; i++ )
	{
		if(vis[i]) continue ;
 
		vector<int> List ;
 
		int x = i , l = i , r = i;
		while(!vis[x])
		{
			vis[x] = true ;
			List.push_back(x) ;
			
			l = min(l,x) ;
			r = max(r,x) ;
 
			x = p[x] ;
		}
 
		for(auto e : List ) intervalo[e] = make_pair(l,r) ;
 
	}
 
	vector<int> dist(n, n+5 ) ;
	priority_queue< pii , vector<pii> , greater<pii> > fila ;
 
	fila.push(make_pair(0,s)) ;
	dist[s] = 0 ;
 
	upd( intervalo[s].ff+1 , intervalo[s].ss ) ;
 
	while(!fila.empty())
	{
		int x = fila.top().ss ;
		int d = fila.top().ff ;
		fila.pop() ;
 
		if(dist[x] != d) continue ;
 
		vector<pii> adj ;
 
		if(x)
		{
			if( qry(x) >= x )
				adj.push_back(make_pair(x-1,0)) ;
			else adj.push_back(make_pair(x-1, 1)) ;
		}
		if(x+1 < n)
		{
			if( qry(x+1) >= x+1)
				adj.push_back(make_pair(x+1, 0)); 
			else adj.push_back(make_pair(x+1, 1 ) ) ;
		}
 
		for(auto e : adj)
		{
			int y = e.ff ;
			int cost = e.ss ;
 
			if(dist[y]<= cost+dist[x]) continue ;
 
			dist[y] = dist[x]+cost ;
 
			fila.push(make_pair(dist[y] , y ));
			upd( intervalo[y].ff+1, intervalo[y].ss ) ;
 
		}
 
	}
 
	ll toSum = dist[L] + dist[R] ;
	ll mx = 0 ;
 
	for(int i = L ; i <= R ; i++ )
		if(intervalo[i].ff <= s && intervalo[i].ss >= s )
			mx = max(mx, dist[i]) ;

	toSum -= mx ;
 
	return ans + 2LL*toSum ;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:131:24: error: no matching function for call to 'max(long long int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
  131 |    mx = max(mx, dist[i]) ;
      |                        ^
In file included from /usr/include/c++/9/vector:60,
                 from books.h:1,
                 from books.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
books.cpp:131:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  131 |    mx = max(mx, dist[i]) ;
      |                        ^
In file included from /usr/include/c++/9/vector:60,
                 from books.h:1,
                 from books.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
books.cpp:131:24: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
  131 |    mx = max(mx, dist[i]) ;
      |                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from books.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
books.cpp:131:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  131 |    mx = max(mx, dist[i]) ;
      |                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from books.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
books.cpp:131:24: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  131 |    mx = max(mx, dist[i]) ;
      |                        ^