Submission #829491

#	Time	Username	Problem	Language	Result	Execution time	Memory
829491		chonka	Sky Walking (IOI19_walk)	C++17	100 / 100	2781 ms	326980 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std ;

const int MAXN = 1e5 + 7 ;
#define fi first
#define se second
typedef long long ll ;
typedef pair < int , int > pii ;

int n ; 

class Tree {
public :
    int mx[ 4 * MAXN ] ;
    void init ( int w , int l , int r , vector < int > &vals ) {
        if ( l == r ) {
            mx[ w ] = vals[ l - 1 ] ;
            return ;
        }
        int mid = ( l + r ) / 2 ;
        init ( 2 * w , l , mid , vals ) ;
        init ( 2 * w + 1 , mid + 1 , r , vals ) ;
        mx[ w ] = max ( mx[ 2 * w ] , mx[ 2 * w + 1 ] ) ;
    }
    int get_l ( int w , int l , int r , int pos , int sr ) {
        if ( pos < l ) { return -1 ; }
        if ( mx[ w ] < sr ) { return -1 ; }
        if ( l == r ) { return l ; }
        int mid = ( l + r ) / 2 ;
        int aux = get_l ( 2 * w + 1 , mid + 1 , r , pos , sr ) ;
        if ( aux != -1 ) { return aux ; }
        return get_l ( 2 * w , l , mid , pos , sr ) ;
    }
    int get_r ( int w , int l , int r , int pos , int sr ) {
        if ( r < pos ) { return -1 ; }
        if ( mx[ w ] < sr ) { return -1 ; }
        if ( l == r ) { return l ; }
        int mid = ( l + r ) / 2 ;
        int aux = get_r ( 2 * w , l , mid , pos , sr ) ;
        if ( aux != -1 ) { return aux ; }
        return get_r ( 2 * w + 1 , mid + 1 , r , pos , sr ) ;
    }
};
Tree w ;

const int coef = 70 ;

int rv[ MAXN ] ;
set < pii > spec[ MAXN ] , scd[ MAXN ] ;
vector < pii > aft[ MAXN ] ;
vector < pii > at_lvl[ MAXN ] ;


vector < pii > v[ coef * MAXN ] ;

void add_edge ( int x , int y , int len ) {
    v[ x ].push_back ( { y , len } ) ;
    v[ y ].push_back ( { x , len } ) ;
}

const ll inf = 1e18 ;
ll dist[ coef * MAXN ] ;

ll dijkstra ( int ori , int targ ) {
    priority_queue < pair < ll , int > > q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        dist[ i ] = inf ;
    }
    dist[ ori ] = 0 ;
    q.push ( { 0 , ori } ) ;
    while ( q.empty ( ) == false ) {
        auto [ cost , x ] = q.top ( ) ;
        q.pop ( ) ;
        cost = -cost ;
        if ( cost != dist[ x ] ) { continue ; }
        for ( auto [ to , add ] : v[ x ] ) {
            if ( dist[ to ] > cost + add ) {
                dist[ to ] = cost + add ;
                q.push ( { -dist[ to ] , to } ) ;
            }
        }
    }
    if ( dist[ targ ] == inf ) { return -1 ; }
    return dist[ targ ] ;
}

vector < int > rem[ MAXN ] , nw[ MAXN ] ;

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
    int len = x.size ( ) ;
    int m = l.size ( ) ;
    map < int , int > foo ;
    for ( int i = 0 ; i < m ; ++ i ) {
        foo[ y[ i ] ] = 0 ;
        nw[ l[ i ] ].push_back ( i ) ;
        rem[ r[ i ] ].push_back ( i ) ;
    }
    int tp = 0 ;
    for ( auto &e : foo ) {
        e.se = ++ tp ;
        rv[ tp ] = e.fi ;
    }
    w.init ( 1 , 1 , len , h ) ;
    for ( int i = 0 ; i < m ; ++ i ) {
        int aux1 = l[ i ] , aux2 = r[ i ] ;
        int act = foo[ y[ i ] ] ;
        for ( auto pt : { s , g } ) { 
            if ( aux1 < pt && pt < aux2 ) {
                int pos1 = w.get_l ( 1 , 1 , len , pt + 1 , y[ i ] ) - 1 ;
                int pos2 = w.get_r ( 1 , 1 , len , pt + 1 , y[ i ] ) - 1 ;
                spec[ pos1 ].insert ( { act , 0 } ) ;
                spec[ pos2 ].insert ( { act , 0 } ) ;
                assert ( h[ pos1 ] >= y[ i ] ) ;
                assert ( h[ pos2 ] >= y[ i ] ) ;
                for ( int j = pos1 + 1 ; j < pt ; ++ j ) {
                    assert ( h[ j ] < y[ i ] ) ;
                }
                for ( int j = pt + 1 ; j < pos2 ; ++ j ) {
                    assert ( h[ j ] < y[ i ] ) ;
                }
            }
        }
        spec[ aux1 ].insert ( { act , 0 } ) ;
        spec[ aux2 ].insert ( { act , 0 } ) ;
    }
    spec[ s ].insert ( { 0 , 0 } ) ;
    spec[ g ].insert ( { 0 , 0 } ) ;
    set < int > op ;
    for ( int i = 0 ; i < len ; ++ i ) {
        for ( auto id : nw[ i ] ) {
            op.insert ( y[ id ] ) ;
        }
        for ( auto [ hh , qq ] : spec[ i ] ) {
            auto it = op.lower_bound ( rv[ hh ] ) ;
            if ( op.size ( ) > 0 && it != op.begin ( ) ) {
                -- it ;
                scd[ i ].insert ( { foo[ *it ] , 0 } ) ;
            }
            it = op.upper_bound ( rv[ hh ] ) ;
            if ( it != op.end ( ) && *it <= h[ i ] ) {
                scd[ i ].insert ( { foo[ *it ] , 0 } ) ;
            }
        }

        for ( auto id : rem[ i ] ) {
            op.erase ( y[ id ] ) ;
        }
        for ( auto id : nw[ i ] ) {
            op.insert ( y[ id ] ) ;
        }

        /**
        for ( auto e : scd[ i ] ) {
            spec[ i ].insert ( e ) ;
        }
        **/
    }
    n = 0 ;
    int ori = -1 , targ = -1 ;
    for ( int i = 0 ; i < len ; ++ i ) {
        for ( auto e : spec[ i ] ) { aft[ i ].push_back ( e ) ; }
        int sz = aft[ i ].size ( ) ;
        for ( int j = 0 ; j < sz ; ++ j ) {
            aft[ i ][ j ].se = ++ n ;
            if ( aft[ i ][ j ].fi == 0 ) {
                if ( i == s ) { ori = n ; }
                else { targ = n ; }
            }
            // at_lvl[ aft[ i ][ j ].fi ].push_back ( { i , n } ) ;
            if ( j > 0 ) {
                add_edge ( aft[ i ][ j - 1 ].se , aft[ i ][ j ].se , rv[ aft[ i ][ j ].fi ] - rv[ aft[ i ][ j - 1 ].fi ] ) ;
            }
        }
        for ( auto e : scd[ i ] ) {
            auto it = spec[ i ].lower_bound ( e ) ;
            if ( it == spec[ i ].end ( ) || it->fi != e.fi ) {
                aft[ i ].push_back ( e ) ;
            }
        }
        sort ( aft[ i ].begin ( ) , aft[ i ].end ( ) ) ;
        sz = aft[ i ].size ( ) ;
        for ( int j = 0 ; j < sz ; ++ j ) {
            if ( aft[ i ][ j ].se == 0 ) { 
                aft[ i ][ j ].se = ++ n ;
            }
            at_lvl[ aft[ i ][ j ].fi ].push_back ( { i , aft[ i ][ j ].se } ) ;
            if ( j > 0 ) {
                add_edge ( aft[ i ][ j - 1 ].se , aft[ i ][ j ].se , rv[ aft[ i ][ j ].fi ] - rv[ aft[ i ][ j - 1 ].fi ] ) ;
            }
        }
    }
    for ( int i = 0 ; i < m ; ++ i ) {
        int aux1 = l[ i ] , aux2 = r[ i ] ;
        int act = foo[ y[ i ] ] ;
        int lo , hi , mid ;
        lo = 0 , hi = at_lvl[ act ].size ( ) - 1 ;
        while ( lo < hi ) {
            mid = ( lo + hi ) / 2 ;
            if ( at_lvl[ act ][ mid ].fi < aux1 ) { lo = mid + 1 ; }
            else { hi = mid ; }
        }
        ++ hi ;
        while ( hi < at_lvl[ act ].size ( ) && at_lvl[ act ][ hi ].fi <= aux2 ) {
            if ( hi >= 1 ) { 
                add_edge ( at_lvl[ act ][ hi - 1 ].se , at_lvl[ act ][ hi ].se , x[ at_lvl[ act ][ hi ].fi ] - x[ at_lvl[ act ][ hi - 1 ].fi ] ) ;
            }
            ++ hi ;
        }
    }
	return dijkstra ( ori , targ ) ;
}

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:204:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         while ( hi < at_lvl[ act ].size ( ) && at_lvl[ act ][ hi ].fi <= aux2 ) {
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43