oj.uz

Submission #540895

# Submission time Handle Problem Language Result Execution time Memory
540895 2022-03-21T23:13:26 Z chonka Road Construction (JOI21_road_construction) C++
100 / 100
 9021 ms 576944 KB 
#include<bits/stdc++.h>
using namespace std ;

#define MAXN 250007

int n , k ;
pair < int , int > a[ MAXN ] ;
int ord[ MAXN ] ;


set < int > ys ;
map < int , int > cm ;

int ctr = 0 ;

priority_queue < long long > hh ;
long long ans[ MAXN ] ;
int mx_coord ;

class Tree {
public :
    multiset < int > small[ 4 * MAXN ] , large[ 4 * MAXN ] ;
    void init ( int where , int IL , int IR ) {
        small[ where ].clear ( ) ;
        large[ where ].clear ( ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        init ( 2 * where , IL , mid ) ;
        init ( 2 * where + 1 , mid + 1 , IR ) ;
    }
    void ins ( int where , int IL , int IR , int pos , int x , int y ) {
        small[ where ].insert ( - x - y ) ;
        large[ where ].insert ( - x + y ) ;
        if ( IL == IR ) { return ; }
        int mid = ( IL + IR ) / 2 ;
        if ( pos <= mid ) {
            ins ( 2 * where , IL , mid , pos , x , y ) ;
        }
        else {
            ins ( 2 * where + 1 , mid + 1 , IR , pos , x , y ) ;
        }
    }
    void proc ( int where , int IL , int IR , int CURL , int CURR , long long fw , bool fl ) {
        if ( IL > IR || CURL > CURR ) { return ; }
        if ( IR < CURL || CURR < IL ) { return ; }
        if ( CURL <= IL && IR <= CURR ) {
            multiset < int > :: iterator it ;
            multiset < int > :: iterator en ;
            if ( fl == true ) { it = small[ where ].begin ( ) , en = small[ where ].end ( ) ; }
            else { it = large[ where ].begin ( ) , en = large[ where ].end ( ) ; }

            while ( it != en ) {
                hh.push ( fw + (*it) ) ;
                while ( hh.size ( ) > k ) {
                    int aux = hh.top ( ) ;
                    hh.pop ( ) ;
                    if ( aux == fw + (*it) ) { return ; }
                }
                ++ it ;
            }
            return ;
        }
        int mid = ( IL + IR ) / 2 ;
        proc ( 2 * where , IL , mid , CURL , CURR , fw , fl ) ;
        proc ( 2 * where + 1 , mid + 1 , IR , CURL , CURR , fw , fl ) ;
    }
};
Tree w ;

bool f ( long long sr , bool inc ) {

    return true ;
}

void input ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].first >> a[ i ].second ;
        ys.insert ( a[ i ].second ) ;
    }
    sort ( a + 1 , a + n + 1 ) ;
    int tp = 0 ;
    for ( auto val : ys ) {
        cm[ val ] = ++ tp ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        ord[ i ] = cm[ a[ i ].second ] ;
    }
    mx_coord = tp ;
}

void solve ( ) {
    w.init ( 1 , 1 , mx_coord ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        w.proc ( 1 , 1 , mx_coord , 1 , ord[ i ] , 0LL + a[ i ].first + a[ i ].second , true ) ;
        w.proc ( 1 , 1 , mx_coord , ord[ i ] + 1 , mx_coord , 0LL + a[ i ].first - a[ i ].second , false ) ;

        w.ins ( 1 , 1 , mx_coord , ord[ i ] , a[ i ].first , a[ i ].second ) ;
    }
    ctr = k ;
    while ( hh.empty ( ) == false ) {
        ans[ ctr -- ] = hh.top ( ) ;
        hh.pop ( ) ;
    }
    for ( int i = 1 ; i <= k ; ++ i ) {
        cout << ans[ i ] << "\n" ;
    }
}

int main ( ) {
    //freopen ( "dictionary.in" , "r" , stdin ) ;
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

Compilation message

road_construction.cpp: In member function 'void Tree::proc(int, int, int, int, int, long long int, bool)':
road_construction.cpp:54:37: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |                 while ( hh.size ( ) > k ) {
      |                         ~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 101840 KB Output is correct
2 Correct 129 ms 101868 KB Output is correct
3 Correct 106 ms 101544 KB Output is correct
4 Correct 101 ms 101540 KB Output is correct
5 Correct 131 ms 100800 KB Output is correct
6 Correct 48 ms 94976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 125948 KB Output is correct
2 Correct 526 ms 126092 KB Output is correct
3 Correct 100 ms 100844 KB Output is correct
4 Correct 486 ms 125900 KB Output is correct
5 Correct 421 ms 126076 KB Output is correct
6 Correct 413 ms 125968 KB Output is correct
7 Correct 433 ms 125136 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7774 ms 565956 KB Output is correct
2 Correct 7849 ms 570928 KB Output is correct
3 Correct 44 ms 94224 KB Output is correct
4 Correct 216 ms 123480 KB Output is correct
5 Correct 3392 ms 336732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7774 ms 565956 KB Output is correct
2 Correct 7849 ms 570928 KB Output is correct
3 Correct 44 ms 94224 KB Output is correct
4 Correct 216 ms 123480 KB Output is correct
5 Correct 3392 ms 336732 KB Output is correct
6 Correct 9021 ms 570848 KB Output is correct
7 Correct 8093 ms 570760 KB Output is correct
8 Correct 51 ms 94292 KB Output is correct
9 Correct 46 ms 94204 KB Output is correct
10 Correct 7899 ms 564856 KB Output is correct
11 Correct 237 ms 123552 KB Output is correct
12 Correct 3378 ms 337252 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 101840 KB Output is correct
2 Correct 129 ms 101868 KB Output is correct
3 Correct 106 ms 101544 KB Output is correct
4 Correct 101 ms 101540 KB Output is correct
5 Correct 131 ms 100800 KB Output is correct
6 Correct 48 ms 94976 KB Output is correct
7 Correct 2894 ms 276860 KB Output is correct
8 Correct 2855 ms 279044 KB Output is correct
9 Correct 101 ms 101564 KB Output is correct
10 Correct 2707 ms 273368 KB Output is correct
11 Correct 2767 ms 270896 KB Output is correct
12 Correct 1207 ms 201032 KB Output is correct
13 Correct 1172 ms 193160 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 101840 KB Output is correct
2 Correct 129 ms 101868 KB Output is correct
3 Correct 106 ms 101544 KB Output is correct
4 Correct 101 ms 101540 KB Output is correct
5 Correct 131 ms 100800 KB Output is correct
6 Correct 48 ms 94976 KB Output is correct
7 Correct 538 ms 125948 KB Output is correct
8 Correct 526 ms 126092 KB Output is correct
9 Correct 100 ms 100844 KB Output is correct
10 Correct 486 ms 125900 KB Output is correct
11 Correct 421 ms 126076 KB Output is correct
12 Correct 413 ms 125968 KB Output is correct
13 Correct 433 ms 125136 KB Output is correct
14 Correct 7774 ms 565956 KB Output is correct
15 Correct 7849 ms 570928 KB Output is correct
16 Correct 44 ms 94224 KB Output is correct
17 Correct 216 ms 123480 KB Output is correct
18 Correct 3392 ms 336732 KB Output is correct
19 Correct 9021 ms 570848 KB Output is correct
20 Correct 8093 ms 570760 KB Output is correct
21 Correct 51 ms 94292 KB Output is correct
22 Correct 46 ms 94204 KB Output is correct
23 Correct 7899 ms 564856 KB Output is correct
24 Correct 237 ms 123552 KB Output is correct
25 Correct 3378 ms 337252 KB Output is correct
26 Correct 2894 ms 276860 KB Output is correct
27 Correct 2855 ms 279044 KB Output is correct
28 Correct 101 ms 101564 KB Output is correct
29 Correct 2707 ms 273368 KB Output is correct
30 Correct 2767 ms 270896 KB Output is correct
31 Correct 1207 ms 201032 KB Output is correct
32 Correct 1172 ms 193160 KB Output is correct
33 Correct 8835 ms 576944 KB Output is correct
34 Correct 8835 ms 576744 KB Output is correct
35 Correct 8554 ms 555100 KB Output is correct
36 Correct 4443 ms 366244 KB Output is correct
37 Correct 4419 ms 366024 KB Output is correct
38 Correct 4116 ms 347100 KB Output is correct