Cod sursa(job #2582473)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 16 martie 2020 19:51:40
Problema Branza Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 1e5 , INF = 1e18 ;
long long aint [ 4 * NMAX + 5 ] , n , t , s ;
pair < long long , long long > data [ NMAX + 5 ] ;

void build ( long long st , long long dr , long long node )
{
    if ( st == dr )
    {
        aint [ node ] = data [ st ].first +  s * ( n - st ) ;
        return ;
    }

    long long med = ( st + dr ) >> 1 ;

    build ( st , med , node * 2 ) ;
    build ( med + 1 , dr , node * 2 + 1 ) ;

    aint [ node ] = min ( aint [ node * 2 ] , aint [ node * 2 + 1 ] ) ;
}

long long query ( long long st , long long dr , long long x , long long y , long long node )
{
    if ( dr < x )
        return INF ;
    if ( st > y )
        return INF ;

    if ( st >= x && dr <= y )
        return aint [ node ] ;

    long long med = ( st + dr ) >> 1 ;

    return min ( query ( st , med , x , y , node * 2 ) , query ( med + 1 , dr , x , y , node * 2 + 1 ) ) ;
}

int main()
{
    freopen ( "branza.in" , "r" , stdin ) ;
    freopen ( "branza.out" , "w" , stdout ) ;

    long long i ;
    unsigned long long ans = 0 ;

    scanf ( "%d%d%d" , & n , & s , & t ) ;

    for ( i = 1 ; i <= n ; ++ i )
        scanf ( "%d%d" , & data [ i ].first , & data [ i ].second ) ;

    build ( 1 , n , 1 ) ;

    for ( i = 1 ; i <= n ; ++ i )
        ans += 1LL * data [ i ].second * ( query ( 1 , n , max ( 1LL , i - t ) , i , 1 ) - 1LL * s * ( n - i ) ) ;

    printf ( "%llu" , ans ) ;
    return 0;
}