Submission #45190

#	Time	Username	Problem	Language	Result	Execution time	Memory
45190		chonka	Building Bridges (CEOI17_building)	C++98	100 / 100	181 ms	21088 KiB

building

#include<iostream>
#include<stdio.h>
#include<set>
using namespace std ;

#define MAXN 100007
#define eps 0.00001

long long inf = (long long)1e18 + 7 ;


int n ;
long long a[ MAXN ] ;
long long b[ MAXN ] ;

long long pref[ MAXN ] ;
long long dp[ MAXN ] ;


struct CHT {
    struct line {
        long long coef , add ;
        double nxt_x ;
        int is_query ;
        line ( ) { coef = add = nxt_x = is_query = 0 ; }
        line ( long long _coef , long long _add ) {
            coef = _coef ;
            add = _add ;
            nxt_x = 0 ;
            is_query = 0 ;
        }
        bool operator < ( const line other ) const {
            if ( is_query == 0 && other.is_query == 0 ) { return ( coef > other.coef ) ; }
            return ( nxt_x < other.nxt_x ) ;
        }
        long long value_at ( long long x ) const {
            return ( x * coef + add ) ;
        }
    };
    bool parallel ( line p1 , line p2 ) {
        return ( p1.coef == p2.coef ) ;
    }
    double intersect ( line p1 , line p2 ) {
        if ( parallel ( p1 , p2 ) == true ) { return inf ; }
        ///printf ( "--- %lld %lld with %lld %lld\n" , p1.coef , p1.add , p2.coef , p2.add ) ;
        return ( ( (double)( p2.add - p1.add ) ) / ( p1.coef - p2.coef ) ) ;
    }
    set < line > s ;
    void init ( ) { s.clear ( ) ; }
    bool has_nxt ( set < line > :: iterator it ) {
        if ( it == s.end ( ) ) { return false ; }
        it ++ ;
        if ( it == s.end ( ) ) { return false ; }
        return true ;
    }
    bool has_prv ( set < line > :: iterator it ) {
        if ( it == s.end ( ) ) { return false ; }
        if ( it == s.begin ( ) ) { return false ; }
        return true ;
    }
    set < line > :: iterator get_nxt ( set < line > :: iterator it ) {
        it ++ ; return it ;
    }
    set < line > :: iterator get_prv ( set < line > :: iterator it ) {
        it -- ; return it ;
    }

    bool needless ( line p1 , line p2 , line p3 ) {
        double cross1 = intersect ( p1 , p2 ) ;
        double cross2 = intersect ( p1 , p3 ) ;
        return ( cross2 < cross1 + eps ) ;
    }
    bool needless ( set < line > :: iterator it ) {
        if ( has_prv ( it ) == false ) { return false ; }
        if ( has_nxt ( it ) == false ) { return false ; }
        return needless ( *get_prv ( it ) , *it , *get_nxt ( it ) ) ;
    }
    set < line > :: iterator update ( set < line > :: iterator it ) {
        line aux = (*it) ;
        double ret = inf ;
        if ( has_nxt ( it ) == true ) { ret = intersect ( (*it) , *get_nxt ( it ) ) ; }
        ///printf ( "%.12f\n" , ret ) ;
        it = s.erase ( it ) ;
        aux.nxt_x = ret ;
        it = s.insert ( it , aux ) ;
        ///printf ( "%.12f\n" , it->nxt_x ) ;
        return it ;
    }
    void add_line ( long long _coef , long long _add ) {
        line nw = line ( _coef , _add ) ;
        set < line > :: iterator it = s.lower_bound ( nw ) ;
        if ( it != s.end ( ) && it->coef == nw.coef ) {
            if ( it->add <= nw.add ) { return ; }
            it = s.erase ( it ) ;
        }
        it = s.insert ( it , nw ) ;
        if ( needless ( it ) == true ) {
            s.erase ( it ) ; return ;
        }
        while ( has_prv ( it ) == true && needless ( get_prv ( it ) ) == true ) { s.erase ( get_prv ( it ) ) ; }
        while ( has_nxt ( it ) == true && needless ( get_nxt ( it ) ) == true ) { s.erase ( get_nxt ( it ) ) ; }

        it = update ( it ) ;
        if ( has_prv ( it ) == true ) { update ( get_prv ( it ) ) ; }
        if ( has_nxt ( it ) == true ) { update ( get_nxt ( it ) ) ; }
    }

    long long query ( long long x ) {
        ///printf ( "SET SIZE EQUALS %d\n" , s.size ( ) ) ;
        line aux = line ( ) ;
        aux.nxt_x = x ;
        aux.is_query = 1 ;
        set < line > :: iterator it = s.lower_bound ( aux ) ;
        if ( it == s.end ( ) ) { return inf ; }
        ///printf ( "--- %f\n" , x ) ;
        return it->value_at ( x ) ;
    }
};

CHT w ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%lld" , &a[ i ] ) ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%lld" , &b[ i ] ) ;
        pref[ i ] = ( pref[ i - 1 ] + b[ i ] ) ;
    }
}

void solve ( ) {
    w.init ( ) ;
    int i ;

    w.add_line ( -2 * a[ 1 ] , a[ 1 ] * a[ 1 ] - pref[ 1 ] ) ;
    for ( i = 2 ; i <= n ; i ++ ) {
        long long ret = w.query ( a[ i ] ) ;
        dp[ i ] = ret + a[ i ] * a[ i ] + pref[ i - 1 ] ;
        ///printf ( "%lld, dp[ %d ] = %lld\n" , ret , i , dp[ i ] ) ;
        w.add_line ( -2 * a[ i ] , dp[ i ] + a[ i ] * a[ i ] - pref[ i ] ) ;
    }
    printf ( "%lld\n" , dp[ n ] ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}
/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/

Compilation message (stderr)

building.cpp: In function 'void input()':
building.cpp:123:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
     ~~~~~~^~~~~~~~~~~~~
building.cpp:126:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld" , &a[ i ] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:129:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld" , &b[ i ] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40