This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009
#define ll long long
#define pb push_back
#define fi first
#define se second
#define left id<<1
#define right id<<1|1
#define re exit(0);
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1
const int mod = 1e9+7 ;
const int INF = 1e9 ;
typedef vector<int> vi ;
typedef pair<int,int> pii ;
typedef vector<pii> vii ;
template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; }
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; }
void add ( int &a , int b )
{
a += b ;
if ( a >= mod ) a -= mod ;
if ( a < 0 ) a += mod ;
}
void rf ()
{
freopen ("bai1.inp","r",stdin) ;
}
int _pow ( int a , int n )
{
if ( n == 0 ) return 1 ;
int res = _pow (a,n/2) ;
if ( n % 2 ) return 1ll*res*res%mod*a%mod ;
else return 1ll*res*res%mod ;
}
int n ;
int a [maxn] ;
vi T [maxn*4] ;
int L [maxn][20] , par [maxn][20] ;
const int LOG = 18 ;
int ver [maxn] ;
void mapping ()
{
vi v ;
for ( int i = 1 ; i <= n ; i ++ ) v . pb (a[i]) ;
sort (v.begin(),v.end()) ;
for ( int i = 1 ; i <= n ; i ++ ) a [i] = _lower(a[i]) , ver[a[i]] = i ;
}
void build_rmq ()
{
for ( int i = 1 ; i <= n ; i ++ ) L [i][0] = a [i] ;
for ( int j = 1 ; j <= LOG ; j ++ )
{
for ( int i = 1 ; i <= n-(1<<j)+1 ; i ++ )
{
L [i][j] = max (L[i][j-1],L[i+(1<<(j-1))][j-1]) ;
}
}
}
vi merge ( vi u , vi v )
{
int i = 0 , j = 0 ;
vi res ;
while ( true )
{
if ( i == u.size() || v [i] > v [j] ) res . pb (v[j++]) ;
else res . pb (v[i++]) ;
if ( i == u.size() && j == v.size() ) return res ;
}
}
void build ( int id , int l , int r )
{
if ( l == r )
{
T [id] . pb (a[l]) ;
return ;
}
int mid = (l+r)/2 ;
build (left,l,mid) ;
build (right,mid+1,r) ;
T [id] = merge (T[left],T[right]) ;
}
void build_segment ()
{
build (1,1,n) ;
}
int get_rmq ( int l , int r )
{
int x = __lg(r-l+1) ;
return max (L[l][x],L[r-(1<<x)+1][x]) ;
}
int get ( int id , int l , int r , int u , int v , int Max )
{
if ( l > v || r < u ) return 0 ;
if ( u <= l && r <= v )
{
if ( T[id][0] < Max )
{
return *--lower_bound(T[id].begin(),T[id].end(),Max) ;
}
return 0 ;
}
int mid = (l+r)/2 ;
return max (get(left,l,mid,u,v,Max),get(right,mid+1,r,u,v,Max)) ;
}
void build_tree ()
{
for ( int i = 1 ; i <= n ; i ++ )
{
if ( i == n ) par [i][0] = n+1 ;
else
{
int l = i+1 , r = n , pos = -1 ;
while ( l <= r )
{
int mid = (l+r)/2 ;
if ( get_rmq (i,mid) > a [i] ) pos = mid , r = mid - 1 ;
else l = mid + 1 ;
}
if ( pos == -1 ) par [i][0] = n+1 ;
else par [i][0] = pos ;
}
}
for ( int j = 1 ; j <= LOG ; j ++ ) for ( int i = 1 ; i <= n ; i ++ )
{
if ( par [i][j-1] == n+1 ) par [i][j] = n+1 ;
else par [i][j] = par[par[i][j-1]][j-1] ;
}
}
void init ( int N , vi H )
{
n = N ;
for ( int i = 1 ; i <= n ; i ++ ) a [i] = H [i-1] ;
mapping () ;
build_rmq () ;
build_segment () ;
build_tree () ;
}
int minimum_jumps ( int l1 , int r1 , int l2 , int r2 )
{
++ l1 , ++ r1 , ++ l2 , ++ r2 ;
int Max = get_rmq (l2,r2) ;
int Min_Max = get (1,1,n,l1,r1,Max) ;
if ( Min_Max == 0 ) return -1 ;
int pos = ver [Min_Max] ;
int l = 1 , r = n ;
int res = INF ;
while ( l <= r )
{
int mid = (l+r)/2 ; int u = pos ;
for ( int i = LOG ; i >= 0 ; i -- ) if ( mid >> i & 1 ) u = par [u][i] ;
if ( u >= l2 && u <= r2 ) chkmin (res,mid) ;
if ( u >= l2 ) r = mid - 1 ;
else l = mid+1 ;
}
return res ;
}
//int main ()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// rf () ;
// int n ; cin >> n ;
// vi H ;
// for ( int i = 1 ; i <= n ; i ++ )
// {
// int x ; cin >> x ;
// H . pb (x) ;
// }
// init (n,H) ;
// cout << minimum_jumps (0,1,2,2) ;
//}
Compilation message (stderr)
jumps.cpp: In function 'vi merge(vi, vi)':
jumps.cpp:73:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if ( i == u.size() || v [i] > v [j] ) res . pb (v[j++]) ;
| ~~^~~~~~~~~~~
jumps.cpp:75:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if ( i == u.size() && j == v.size() ) return res ;
| ~~^~~~~~~~~~~
jumps.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | if ( i == u.size() && j == v.size() ) return res ;
| ~~^~~~~~~~~~~
jumps.cpp: In function 'void rf()':
jumps.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | freopen ("bai1.inp","r",stdin) ;
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |