oj.uz

Submission #890504

# Submission time Handle Problem Language Result Execution time Memory
890504 2023-12-21T10:51:01 Z LucaIlie Road Construction (JOI21_road_construction) C++17
0 / 100
 4046 ms 11588 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;
};

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 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;

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 = 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;

    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 } );
            points.update( v[j].x - v[j].y, -1 );
            j++;
        }

        auto it = s.lower_bound( { 0, 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 );
    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:51: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]
   51 |         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:66: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]
   66 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:161: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]
  161 |     while ( sol.size() < k )
      |             ~~~~~~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2726 ms 11588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4046 ms 8924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4046 ms 8924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5832 KB Output isn't correct
2 Halted 0 ms 0 KB -