Submission #238940

#	Time	Username	Problem	Language	Result	Execution time	Memory
238940		DodgeBallMan	Pinball (JOI14_pinball)	C++14	100 / 100	343 ms	26732 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int n, m, a[N], b[N], c[N];
long long d[N], t1[N*4], t2[N*4], ans = 1e18;
vector<int> coord;

void update( long long t[], int x, long long va, int l = 1, int r = coord.size(), int idx = 1 ) {
    if( l == r ) return void( t[idx] = min( t[idx], va ) );
    int mid = l + r >> 1;
    if( x <= mid ) update( t, x, va, l, mid, idx<<1 );
    else update( t, x, va, mid+1, r, idx<<1|1 );
    t[idx] = min( t[idx<<1], t[idx<<1|1] );
}

long long query( long long t[], int ll, int rr, int l = 1, int r = coord.size(), int idx = 1 ) {
    //printf("%d %d L : %d R : %d %lld\n",ll,rr,l,r,t[idx]);
    if( l > rr || r < ll ) return 1e18;
    if( l >= ll && r <= rr ) return t[idx];
    int mid = l + r >> 1;
    return min( query( t, ll, rr, l, mid, idx<<1 ), query( t, ll, rr, mid+1, r, idx<<1|1 ) );
}

int get( int x ) { return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + 1; }

int main()
{
    fill( t1, t1 + N*4, 1e18 ), fill( t2, t2 + N*4, 1e18 );
    scanf("%d %d",&m,&n);
    coord.emplace_back( 1 ), coord.emplace_back( n );
    for( int i = 1 ; i <= m ; i++ ) {
        scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
        coord.emplace_back( a[i] ), coord.emplace_back( b[i] ), coord.emplace_back( c[i] );
    }
    sort( coord.begin(), coord.end() );
    coord.resize( unique( coord.begin(), coord.end() ) - coord.begin() );
    /*for( int i : coord ) printf("%d ",i);
    printf("\n");*/
    update( t1, 1, 0 ), update( t2, coord.size(), 0 );
    for( int i = 1 ; i <= m ; i++ ) {
        int l = get( a[i] ), r = get( b[i] ), x = get( c[i] );
        //printf("%d %d %d\n",l,r,x);
        long long pre = query( t1, l, r ), suf = query( t2, l, r ); 
        ans = min( ans, pre + suf + d[i] );
        //printf("%lld %lld\n",pre,suf);
        update( t1, x, pre + d[i] ), update( t2, x, suf + d[i] );
    }
    if( ans == 1e18 ) printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void update(long long int*, int, long long int, int, int, int)':
pinball.cpp:12:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
pinball.cpp: In function 'long long int query(long long int*, int, int, int, int, int)':
pinball.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
pinball.cpp: In function 'int main()':
pinball.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m,&n);
     ~~~~~^~~~~~~~~~~~~~~
pinball.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49