oj.uz

답안 #890279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890279 2023-12-20T22:56:44 Z LucaIlie Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 173260 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

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() );
        for ( int i = 0; i < pos.size(); i++ )
            aib.push_back( 0 );
    }

    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;
        }
        if ( pos[l] != i )
            exit( 1 );
        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;
    }
};

struct AIB2D {
    vector<int> pos;
    vector<AIB> aib;
    vector<point> pts;
    AIB emptyAIB;

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

    void add( int i, int j ) {
        pts.push_back( { i, j } );
        pos.push_back( i );
        emptyAIB.init();
    }

    void prep() {
        pos.push_back( -INF );
        sort( pos.begin(), pos.end() );
        pos.resize( unique( pos.begin(), pos.end() ) - pos.begin() );
        for ( int i = 0; i < pos.size(); i++ )
            aib.push_back( emptyAIB );
        for ( point q: pts ) {
            int l = 0, r = pos.size();
            while ( r - l > 1 ) {
                int p = (l + r) / 2;
                if ( pos[p] > q.x )
                    r = p;
                else
                    l = p;
            }
            int i = l;
            while ( i < aib.size() ) {
                aib[i].add( q.y );
                i += (i & -i);
            }
        }
        for ( int i = 0; i < pos.size(); i++ )
            aib[i].prep();
    }

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

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

    int query( int i, int 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].query( j );
            i -= (i & -i);
        }
        return s;
    }
} leftPoints, rightPoints;

signed main() {
    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, -v[i].x - v[i].y );
        rightPoints.add( v[i].y, -v[i].x + v[i].y );
    }
    leftPoints.prep();
    rightPoints.prep();

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

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

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

    vector<int> 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( int x: sol )
        cout << x << "\n";

    return 0;
}

Compilation message

road_construction.cpp: In member function 'void AIB::prep()':
road_construction.cpp:33: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]
   33 |         for ( int i = 0; i < pos.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB::clear()':
road_construction.cpp:38: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]
   38 |         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:54: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]
   54 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB2D::prep()':
road_construction.cpp:100: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]
  100 |         for ( int i = 0; i < pos.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp:112:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<AIB>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while ( i < aib.size() ) {
      |                     ~~^~~~~~~~~~~~
road_construction.cpp:117: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]
  117 |         for ( int i = 0; i < pos.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB2D::clear()':
road_construction.cpp:122:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<AIB>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for ( int i = 0; i < aib.size(); i++ )
      |                          ~~^~~~~~~~~~~~
road_construction.cpp: In member function 'void AIB2D::update(long long int, long long int, long long int)':
road_construction.cpp:136:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<AIB>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         while ( i < aib.size() ) {
      |                 ~~^~~~~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:214: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]
  214 |     while ( sol.size() < k )
      |             ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 5572 KB Output is correct
2 Correct 73 ms 5452 KB Output is correct
3 Correct 59 ms 5560 KB Output is correct
4 Correct 54 ms 5308 KB Output is correct
5 Correct 72 ms 4420 KB Output is correct
6 Correct 17 ms 604 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10067 ms 26548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10022 ms 173260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10022 ms 173260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 5572 KB Output is correct
2 Correct 73 ms 5452 KB Output is correct
3 Correct 59 ms 5560 KB Output is correct
4 Correct 54 ms 5308 KB Output is correct
5 Correct 72 ms 4420 KB Output is correct
6 Correct 17 ms 604 KB Output is correct
7 Execution timed out 10028 ms 71200 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 5572 KB Output is correct
2 Correct 73 ms 5452 KB Output is correct
3 Correct 59 ms 5560 KB Output is correct
4 Correct 54 ms 5308 KB Output is correct
5 Correct 72 ms 4420 KB Output is correct
6 Correct 17 ms 604 KB Output is correct
7 Execution timed out 10067 ms 26548 KB Time limit exceeded
8 Halted 0 ms 0 KB -