Submission #890501

#	Time	Username	Problem	Language	Result	Execution time	Memory
890501		LucaIlie	Road Construction (JOI21_road_construction)	C++17	7 / 100	4006 ms	13504 KiB

road_construction

#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<int> 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] = 0;
    }

    void update( int i, int 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] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        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];
            i -= (i & -i);
        }
        return s;
    }
} points;

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 + a.y == b.x + b.y )
            return a.x - a.y < b.x - b.y;
        return a.x + a.y < b.x + b.y;
    } );


    points.init();
    for ( int i = 0; i < n; i++ )
        points.add( v[i].x - v[i].y );
    points.prep();

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

        long long pairs = 0;
        points.clear();
        int j = 0;
        for ( int i = 0; i < n; i++ ) {
            while ( (v[i].x + v[i].y) - (v[j].x + v[j].y) > d ) {
                points.update( v[j].x - v[j].y, -1 );
                j++;
            }

            pairs += points.query( v[i].x - v[i].y + d ) - points.query( v[i].x - v[i].y - d - 1 );

            points.update( v[i].x - v[i].y, 1 );
        }

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

    vector<long long> sol;
    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 (stderr)

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<long long int>::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<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:130: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]
  130 |     while ( sol.size() < k )
      |             ~~~~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35