oj.uz

Submission #829462

# Submission time Handle Problem Language Result Execution time Memory
829462 2023-08-18T11:02:04 Z chonka Sky Walking (IOI19_walk) C++17
25 / 100
 1460 ms 287732 KB 
#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 ] + 1 ].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 } ) ;
            }
        }
        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 : rem[ i ] ) {
            op.erase ( y[ id ] ) ;
        }
        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 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

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:191: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]
  191 |         while ( hi < at_lvl[ act ].size ( ) && at_lvl[ act ][ hi ].fi <= aux2 ) {
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 183372 KB Output is correct
2 Correct 87 ms 183468 KB Output is correct
3 Correct 82 ms 183480 KB Output is correct
4 Correct 82 ms 183488 KB Output is correct
5 Correct 81 ms 183520 KB Output is correct
6 Correct 81 ms 183476 KB Output is correct
7 Correct 83 ms 183484 KB Output is correct
8 Correct 85 ms 183500 KB Output is correct
9 Correct 82 ms 183392 KB Output is correct
10 Correct 84 ms 183488 KB Output is correct
11 Correct 81 ms 183456 KB Output is correct
12 Correct 81 ms 183392 KB Output is correct
13 Correct 85 ms 183444 KB Output is correct
14 Correct 81 ms 183504 KB Output is correct
15 Correct 81 ms 183492 KB Output is correct
16 Correct 82 ms 183480 KB Output is correct
17 Correct 80 ms 183444 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 183408 KB Output is correct
2 Correct 83 ms 183440 KB Output is correct
3 Correct 806 ms 262152 KB Output is correct
4 Correct 741 ms 266804 KB Output is correct
5 Correct 505 ms 247240 KB Output is correct
6 Correct 507 ms 243792 KB Output is correct
7 Correct 501 ms 247516 KB Output is correct
8 Correct 897 ms 266684 KB Output is correct
9 Correct 663 ms 261592 KB Output is correct
10 Correct 782 ms 268636 KB Output is correct
11 Correct 665 ms 250964 KB Output is correct
12 Correct 502 ms 243744 KB Output is correct
13 Correct 911 ms 271432 KB Output is correct
14 Correct 461 ms 234700 KB Output is correct
15 Correct 432 ms 234876 KB Output is correct
16 Incorrect 363 ms 234976 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 196312 KB Output is correct
2 Correct 1018 ms 279496 KB Output is correct
3 Correct 1099 ms 281632 KB Output is correct
4 Correct 1328 ms 287308 KB Output is correct
5 Correct 1317 ms 287148 KB Output is correct
6 Correct 1460 ms 284112 KB Output is correct
7 Correct 500 ms 238672 KB Output is correct
8 Correct 646 ms 243796 KB Output is correct
9 Correct 1382 ms 279860 KB Output is correct
10 Correct 542 ms 247576 KB Output is correct
11 Correct 97 ms 185548 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 196312 KB Output is correct
2 Correct 1018 ms 279496 KB Output is correct
3 Correct 1099 ms 281632 KB Output is correct
4 Correct 1328 ms 287308 KB Output is correct
5 Correct 1317 ms 287148 KB Output is correct
6 Correct 1460 ms 284112 KB Output is correct
7 Correct 500 ms 238672 KB Output is correct
8 Correct 646 ms 243796 KB Output is correct
9 Correct 1382 ms 279860 KB Output is correct
10 Correct 542 ms 247576 KB Output is correct
11 Correct 97 ms 185548 KB Output is correct
12 Correct 1050 ms 281276 KB Output is correct
13 Correct 954 ms 286148 KB Output is correct
14 Correct 1253 ms 287000 KB Output is correct
15 Correct 766 ms 263524 KB Output is correct
16 Correct 712 ms 269076 KB Output is correct
17 Correct 809 ms 280788 KB Output is correct
18 Correct 780 ms 263576 KB Output is correct
19 Correct 721 ms 268848 KB Output is correct
20 Correct 528 ms 237592 KB Output is correct
21 Correct 110 ms 188952 KB Output is correct
22 Correct 660 ms 262748 KB Output is correct
23 Correct 602 ms 259532 KB Output is correct
24 Correct 485 ms 242096 KB Output is correct
25 Correct 547 ms 254844 KB Output is correct
26 Correct 442 ms 234696 KB Output is correct
27 Correct 1210 ms 287732 KB Output is correct
28 Correct 859 ms 284952 KB Output is correct
29 Correct 1282 ms 283124 KB Output is correct
30 Correct 515 ms 238396 KB Output is correct
31 Correct 1147 ms 279880 KB Output is correct
32 Correct 444 ms 239648 KB Output is correct
33 Incorrect 431 ms 240248 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 183372 KB Output is correct
2 Correct 87 ms 183468 KB Output is correct
3 Correct 82 ms 183480 KB Output is correct
4 Correct 82 ms 183488 KB Output is correct
5 Correct 81 ms 183520 KB Output is correct
6 Correct 81 ms 183476 KB Output is correct
7 Correct 83 ms 183484 KB Output is correct
8 Correct 85 ms 183500 KB Output is correct
9 Correct 82 ms 183392 KB Output is correct
10 Correct 84 ms 183488 KB Output is correct
11 Correct 81 ms 183456 KB Output is correct
12 Correct 81 ms 183392 KB Output is correct
13 Correct 85 ms 183444 KB Output is correct
14 Correct 81 ms 183504 KB Output is correct
15 Correct 81 ms 183492 KB Output is correct
16 Correct 82 ms 183480 KB Output is correct
17 Correct 80 ms 183444 KB Output is correct
18 Correct 85 ms 183408 KB Output is correct
19 Correct 83 ms 183440 KB Output is correct
20 Correct 806 ms 262152 KB Output is correct
21 Correct 741 ms 266804 KB Output is correct
22 Correct 505 ms 247240 KB Output is correct
23 Correct 507 ms 243792 KB Output is correct
24 Correct 501 ms 247516 KB Output is correct
25 Correct 897 ms 266684 KB Output is correct
26 Correct 663 ms 261592 KB Output is correct
27 Correct 782 ms 268636 KB Output is correct
28 Correct 665 ms 250964 KB Output is correct
29 Correct 502 ms 243744 KB Output is correct
30 Correct 911 ms 271432 KB Output is correct
31 Correct 461 ms 234700 KB Output is correct
32 Correct 432 ms 234876 KB Output is correct
33 Incorrect 363 ms 234976 KB Output isn't correct
34 Halted 0 ms 0 KB -