Submission #294818

#TimeUsernameProblemLanguageResultExecution timeMemory
294818infinite_iqPinball (JOI14_pinball)C++14
100 / 100
961 ms53004 KiB
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0) #include <bits/stdc++.h> using namespace std; #define sqr 100 #define mp make_pair #define mid (l+r)/2 #define le node * 2 #define ri node * 2 + 1 #define pb push_back #define ppb pop_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define ins insert #define era erase //#define C continue #define mem(dp,i) memset(dp,i,sizeof(dp)) #define mset multiset #define all(x) x.begin(), x.end() #define gc getchar_unlocked typedef long long ll; typedef short int si; typedef double ld; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll; typedef pair<double,ll>pdi; const ll inf=2e18; const ll mod=1e9+7; const ld Pi=acos(-1) ; ll n , m , M ; set < ll > s ; unordered_map < ll , ll > id ; ll A [100009] , B [100009] , C [100009] , D [100009] , Dp [100009][2] ; void Compress () { for ( int i = 0 ; i < n ; i ++ ) { s .ins ( A [i] ) ; s .ins ( B [i] ) ; s .ins ( C [i] ) ; } s .ins (1) ; s .ins (M) ; for ( auto u : s ) { id [u] = ++ m ; } for ( int i = 0 ; i < n ; i ++ ) { A [i] = id [ A [i] ] ; B [i] = id [ B [i] ] ; C [i] = id [ C [i] ] ; } } ll tree [4000009][2] ; void build ( int node , int l , int r ) { tree [node][0] = tree [node][1] = inf ; if ( l == r ) return ; build ( le , l , mid ) ; build ( ri , mid + 1 , r ) ; } void upd ( int node , int l , int r , int id , ll val , int x ) { if ( l == r ) { tree [node][x] = min ( tree [node][x] , val ) ; return ; } if ( id <= mid ) upd ( le , l , mid , id , val , x ) ; else upd ( ri , mid + 1 , r , id , val , x ) ; for ( int i = 0 ; i < 2 ; i ++ ) { tree [node][i] = min ( tree [le][i] , tree [ri][i] ) ; } } ll query ( int node , int l , int r , int s , int e , int x ) { if ( s > r || e < l ) return inf ; if ( s <= l && e >= r ) return tree [node][x] ; return min ( query ( le , l , mid , s , e , x ) , query ( ri , mid + 1 , r , s , e , x ) ) ; } int main () { cin >> n >> M ; for ( int i = 0 ; i < n ; i ++ ) { cin >> A [i] >> B [i] >> C [i] >> D [i] ; } Compress () ; build ( 1 , 0 , m ) ; for ( int i = 0 ; i < n ; i ++ ) { Dp [i][0] = ( A [i] == 1 ? D [i] : inf ) ; Dp [i][1] = ( B [i] == m ? D [i] : inf ) ; for ( int j = 0 ; j < 2 ; j ++ ) { Dp [i][j] = min ( Dp [i][j] , query ( 1 , 0 , m , A [i] , B [i] , j ) + D [i] ) ; } for ( int j = 0 ; j < 2 ; j ++ ) { upd ( 1 , 0 , m , C [i] , Dp [i][j] , j ) ; } } ll ans = inf ; for ( int i = 0 ; i < n ; i ++ ) { ans = min ( ans , Dp [i][0] + Dp [i][1] - D [i] ) ; } cout << ( ans >= inf ? -1 : ans ) << endl ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...