oj.uz

Submission #890479

# Submission time Handle Problem Language Result Execution time Memory
890479 2023-12-21T10:03:14 Z LucaIlie Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 340392 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

struct point {
    int x, y;
};

const int MAX_N = 2.5e5;
const int MAX_X = 1e9;
const int INF = 2e9 + 1;
point v[MAX_N];

struct AIB {
    vector<int> pos;
    vector<ordered_set> aib;

    void init() {
        pos.clear();
        aib.clear();
    }

    void add( int i ) {
        pos.push_back( i );
    }

    void prep() {
        pos.push_back( -INF );
        sort( pos.begin(), pos.end() );
        pos.resize( unique( pos.begin(), pos.end() ) - pos.begin() );
        aib.resize( pos.size() );
    }

    void clear() {
        for ( int i = 0; i < aib.size(); i++ )
            aib[i].clear();
    }

    void update( int i, long long x ) {
        int l = 0, r = pos.size();
        while ( r - l > 1 ) {
            int p = (l + r) / 2;
            if ( pos[p] > i )
                r = p;
            else
                l = p;
        }

        i = l;
        while ( i < aib.size() ) {
            aib[i].insert( x );
            i += (i & -i);
        }
    }

    int query( int i, long long j ) {
        int l = 0, r = pos.size();
        while ( r - l > 1 ) {
            int p = (l + r) / 2;
            if ( pos[p] > i )
                r = p;
            else
                l = p;
        }
        i = l;
        int s = 0;
        while ( i > 0 ) {
            s += aib[i].order_of_key( j + 1 );
            i -= (i & -i);
        }
        return s;
    }
} leftPoints, rightPoints;

signed main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    cout.tie( NULL );

    int n, k;

    cin >> n >> k;
    for ( int i = 0; i < n; i++ )
        cin >> v[i].x >> v[i].y;

    sort( v, v + n, []( point a, point b ) {
        if ( a.x == b.x )
            return a.y < b.y;
        return a.x < b.x;
    } );


    leftPoints.init();
    rightPoints.init();
    for ( int i = 0; i < n; i++ ) {
        leftPoints.add( v[i].y );
        rightPoints.add( v[i].y );
    }
    leftPoints.prep();
    rightPoints.prep();

    long long ld = 0, rd = 2LL * INF;
    while ( rd - ld > 1 ) {
        long long d = (ld + rd) / 2;

        long long pairs = 0;
        leftPoints.clear();
        rightPoints.clear();
        for ( int i = 0; i < n; i++ ) {
            pairs += leftPoints.query( v[i].y, d - (v[i].x + v[i].y) );
            pairs += rightPoints.query( MAX_X, d - (v[i].x - v[i].y) ) - rightPoints.query( v[i].y, d - (v[i].x - v[i].y) );

            leftPoints.update( v[i].y, -v[i].x - v[i].y );
            rightPoints.update( v[i].y, -v[i].x + v[i].y );
        }

        if ( pairs < k )
            ld = d;
        else
            rd = d;
    }
    long long d = rd;


    vector<long long> sol;
    for ( int i = 0; i < n; i++ ) {
        for ( int j = i + 1; j < n; j++ ) {
            if ( abs( v[i].x - v[j].x ) + abs( v[i].y - v[j].y ) < d )
                sol.push_back( abs( v[i].x - v[j].x ) + abs( v[i].y - v[j].y ) );
        }
    }

    while ( sol.size() < k )
        sol.push_back( d );
    sort( sol.begin(), sol.end() );
    for( long long x: sol )
        cout << x << "\n";

    return 0;
}

Compilation message

road_construction.cpp: In member function 'void AIB::clear()':
road_construction.cpp:41:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<__gnu_pbds::tree<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for ( int i = 0; i < aib.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB::update(long long int, long long int)':
road_construction.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<__gnu_pbds::tree<long long int, __gnu_pbds::null_type, std::less<long long int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:139:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  139 |     while ( sol.size() < k )
      |             ~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5824 KB Output is correct
2 Correct 103 ms 5792 KB Output is correct
3 Correct 68 ms 5736 KB Output is correct
4 Correct 67 ms 5732 KB Output is correct
5 Incorrect 88 ms 4788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10032 ms 39600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10047 ms 340392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10047 ms 340392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5824 KB Output is correct
2 Correct 103 ms 5792 KB Output is correct
3 Correct 68 ms 5736 KB Output is correct
4 Correct 67 ms 5732 KB Output is correct
5 Incorrect 88 ms 4788 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5824 KB Output is correct
2 Correct 103 ms 5792 KB Output is correct
3 Correct 68 ms 5736 KB Output is correct
4 Correct 67 ms 5732 KB Output is correct
5 Incorrect 88 ms 4788 KB Output isn't correct
6 Halted 0 ms 0 KB -