제출 #236395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236395		AS82	Pinball (JOI14_pinball)	C++14	100 / 100	309 ms	17948 KiB

pinball

// In the Name of Allah
// Ya Ali

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define all( x ) x.begin() , x.end()
#define pb push_back
#define mp make_pair

const int maxn = 1e5 + 10 ;
const int INF = 1e18 ;

int n , m , ind[ maxn ] , a[ maxn ] , b[ maxn ] , c[ maxn ] , d[ maxn ] , l1[ maxn ] , r1[ maxn ] , ans = INF ;
int mn1[ 4*maxn ] , mn2[ 4*maxn ] ;
vector< pair< int , int > > vv ;

void build()
{
  for(int i = 0 ; i <= 4*m ; i ++)
    mn1[ i ] = mn2[ i ] = INF;
}

int ask1( int x , int y , int l = 0 , int r = m-1 , int node = 1 )
{
  if( l > y || r < x )
    return INF ;
  if( l >= x && r <= y )
    return mn1[ node ];

  int mid = (r+l)/2 ;
  return min( ask1( x , y , l , mid , 2*node ) , ask1( x , y , mid+1 , r , (2*node)+1 ) ) ;
}
int ask2( int x , int y , int l = 0 , int r = m-1 , int node = 1 )
{
  if( l > y || r < x )
    return INF ;
  if( l >= x && r <= y )
    return mn2[ node ];

  int mid = (r+l)/2 ;
  return min( ask2( x , y , l , mid , 2*node ) , ask2( x , y , mid+1 , r , (2*node)+1 ) ) ;
}

void up1( int x , int y , int va , int l = 0 , int r = m-1 , int node = 1 )
{
  if( l > y || r < x )
    return;
  if( l >= x && r <= y ){
    mn1[ node ] = va ;
    return ;
  }

  int mid = (r+l)/2;
  up1( x , y , va , l , mid , 2*node ) ;
  up1( x , y , va , mid+1 , r , (2*node)+1 ) ;
  mn1[ node ] = min( mn1[ 2*node ] , mn1[ (2*node)+1 ] ) ;
}

void up2( int x , int y , int va , int l = 0 , int r = m-1 , int node = 1 )
{
  if( l > y || r < x )
    return;
  if( l >= x && r <= y ){
    mn2[ node ] = va ;
    return ;
  }

  int mid = (r+l)/2;
  up2( x , y , va , l , mid , 2*node ) ;
  up2( x , y , va , mid+1 , r , (2*node)+1 ) ;
  mn2[ node ] = min( mn2[ 2*node ] , mn2[ (2*node)+1 ] ) ;
}

signed main()
{
ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;

cin >> m >> n ;
for(int i = 1 ; i <= m ; i ++){
  cin >> a[ i ] >> b[ i ] >> c[ i ] >> d[ i ];
  vv.pb({ c[ i ] , i }) ;
}

sort( all( vv ) ) ;
for(int i = 0 ; i < m ; i ++)
  ind[ vv[ i ].S ] = i ;

for(int i = 1 ; i <= m ; i ++){
  l1[ i ] = lower_bound( all( vv ) , mp( a[ i ] , 0ll ) ) - vv.begin();
  r1[ i ] = upper_bound( all( vv ) , mp( b[ i ] , INF ) ) - vv.begin();
  r1[ i ] -- ;
}

build();

for(int i = 1 ; i <= m ; i ++){

//for dp1
 int x = INF ;

 if( a[ i ] == 1 )x = d[ i ] ;
 x = min( x , ask1( l1[ i ] , r1[ i ] ) + d[ i ] ) ;
 up1( ind[ i ] , ind[ i ] , x ) ;

// for dp2
 x = INF ;

 if( b[ i ] == n )x = d[ i ] ;
 x = min( x , ask2( l1[ i ] , r1[ i ] ) + d[ i ] ) ;
 up2( ind[ i ] , ind[ i ] , x );

  if( a[ i ] > 1 && b[ i ] < n )ans = min( ans , ask1( l1[ i ] , r1[ i ] ) + ask2( l1[ i ] , r1[ i ] ) + d[ i ] ) ;
  if( a[ i ] == 1 && b[ i ] < n )ans = min( ans , ask2( l1[ i ] , r1[ i ] ) + d[ i ] ) ;
  if( a[ i ] > 1 && b[ i ] == n )ans = min( ans , ask1( l1[ i ] , r1[ i ] ) + d[ i ] ) ;
  if( a[ i ] == 1 && b[ i ] == n )ans = min( ans , d[ i ] ) ;
}

if( ans == INF )cout << -1 ;
else cout << ans ;

    return 0;
}

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