oj.uz

Submission #294818

# Submission time Handle Problem Language Result Execution time Memory
294818 2020-09-09T09:46:10 Z infinite_iq Pinball (JOI14_pinball) C++14
100 / 100
 961 ms 53004 KB 
#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 ;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 5 ms 768 KB Output is correct
24 Correct 6 ms 744 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 5 ms 640 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 6 ms 768 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 3 ms 512 KB Output is correct
22 Correct 6 ms 768 KB Output is correct
23 Correct 5 ms 768 KB Output is correct
24 Correct 6 ms 744 KB Output is correct
25 Correct 49 ms 3704 KB Output is correct
26 Correct 161 ms 9464 KB Output is correct
27 Correct 462 ms 19264 KB Output is correct
28 Correct 455 ms 8976 KB Output is correct
29 Correct 336 ms 16872 KB Output is correct
30 Correct 512 ms 11604 KB Output is correct
31 Correct 792 ms 32384 KB Output is correct
32 Correct 687 ms 23512 KB Output is correct
33 Correct 103 ms 9220 KB Output is correct
34 Correct 396 ms 26848 KB Output is correct
35 Correct 671 ms 52880 KB Output is correct
36 Correct 961 ms 52916 KB Output is correct
37 Correct 836 ms 53004 KB Output is correct
38 Correct 788 ms 52936 KB Output is correct