Submission #890507

#	Time	Username	Problem	Language	Result	Execution time	Memory
890507		LucaIlie	Road Construction (JOI21_road_construction)	C++17	100 / 100	4747 ms	17252 KiB

road_construction

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct point {
    int x, y;
};

struct aa {
    int i, val;

    bool operator < ( const aa &a ) const {
        if ( val == a.val )
            return i < a.i;
        return val < a.val;
    }
};

const int MAX_N = 2.5e5;
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;

set<aa> s;

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 = 2 * 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 = ld;

    vector<long long> sol;

    int j = 0;
    for ( int i = 0; i < n; i++ ) {
        while ( (v[i].x + v[i].y) - (v[j].x + v[j].y) > d ) {
            s.erase( { j, v[j].x - v[j].y } );
            j++;
        }

        auto it = s.lower_bound( { -1, v[i].x - v[i].y - d } );
        while ( it != s.end() && it->val <= v[i].x - v[i].y + d ) {
            int j = it->i;
            sol.push_back( abs( v[i].x - v[j].x ) + abs( v[i].y - v[j].y ) );
            it++;
        }

        s.insert( { i, v[i].x - v[i].y } );
    }

    while ( sol.size() < k )
        sol.push_back( d + 1 );
    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:46: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]
   46 |         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:61: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]
   61 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:155: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]
  155 |     while ( sol.size() < k )
      |             ~~~~~~~~~~~^~~

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