Submission #432262

#	Time	Username	Problem	Language	Result	Execution time	Memory
432262		blue	Road Construction (JOI21_road_construction)	C++17	5 / 100	10096 ms	38444 KiB

road_construction

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

/*
We transform each point (x, y) into a point (x', y') where x' = x+y and y' = x-y. The Manhattan
distance between (x1, y1) and (x2, y2) = |x1-x2| + |y1-y2| = max( |x1'-x2'|, |y1'-y2'| ).

1. Transform each point (x, y) into a point (x1, y1) where x1 = x+y and y1 = x-y. √
2. Sort the points (x1, y1) twice, once by x1 and once by y1. √
3. Iterate over points sorted by x1:
4.      Maintain a set of these points sorted by the distance to the closest neighbor.
5.      Repeatedly, find the smallest such distance.
6.      If this distance is larger than the X-Y distance, add it to the result set.
*/

long long long_absval(long long x)
{
    return max(x, -x);
}

const int maxN = 250000;
const long long INF = 1'000'000'000'000'000'000LL;

vector<long long> A(1+maxN), B(1+maxN);
vector<int> I_A, I_B;

int N, K;

struct loc
{
    int i;
    long long v;
};

bool operator < (loc P, loc Q)
{
    if(P.v == Q.v) return P.i < Q.i;
    return P.v < Q.v;
}


vector<int> nxt;
vector<long long> val;

void compute_score_A(int i)
{
    val[i] = INF;
    if(nxt[i] <= N-1)
    {
        val[i] = A[ I_A[nxt[i]] ] - A[ I_A[i] ];
    }
}

void compute_score_B(int i)
{
    val[i] = INF;

    if(nxt[i] <= N-1)
    {
        val[i] = B[ I_B[nxt[i]] ] - B[ I_B[i] ];
    }
}

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

    cin >> N >> K;

    for(int i = 1; i <= N; i++)
    {
        long long X, Y;
        cin >> X >> Y;
        A[i] = X+Y;
        B[i] = X-Y;
    }

    I_A = I_B = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        I_A[i] = i+1;
        I_B[i] = i+1;
    }

    sort(I_A.begin(), I_A.end(), [] (int p, int q)
    {
        return A[p] < A[q];
    });

    sort(I_B.begin(), I_B.end(), [] (int p, int q)
    {
        return B[p] < B[q];
    });

    multiset<long long> res;



    // cerr << "check\n";


    //Part 1: iterate over I_A;
    nxt = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        nxt[i] = i+1;
    }

    val = vector<long long>(N, INF);
    for(int i = 0; i < N; i++)
    {
        compute_score_A(i);
    }

    set<loc> L;
    for(int i = 0; i < N; i++) L.insert(loc{i, val[i]});

    while(res.size() < K)
    {
        int i = L.begin()->i;

        L.erase(L.begin());

        // cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';

        if(val[i] >= INF) break;

        int j = nxt[i];               //!!!!!
        if(long_absval(A[ I_A[i] ] - A[ I_A[j] ]) >= long_absval(B[ I_A[i] ] - B[ I_A[j] ]))
        {
            res.insert(long_absval(A[ I_A[i] ] - A[ I_A[j] ]));
            // cerr << I_A[i] << ' ' << I_A[j] << ' ' << abs(A[ I_A[i] ] - A[ I_A[j] ]) << '\n';
        }
        nxt[i]++;
        compute_score_A(i);

        L.insert(loc{i, val[i]});
    }












    // cerr << "switching \n";





    //Part 2: iterate over I_B;
    nxt = vector<int>(N);
    for(int i = 0; i < N; i++)
    {
        nxt[i] = i+1;
    }

    val = vector<long long>(N, INF);
    for(int i = 0; i < N; i++)
    {
        compute_score_B(i);
    }

    L.clear();
    for(int i = 0; i < N; i++) L.insert(loc{i, val[i]});

    // cerr << "hello\n";

    while(res.size() < 2*K)
    {
        int i = L.begin()->i;

        L.erase(L.begin());

        int j = nxt[i];               //!!!!!

        // cerr << i << ' ' << val[i] << ' ' << nxt[i] << '\n';

        if(val[i] >= INF) break;
        if(long_absval(B[ I_B[i] ] - B[ I_B[j] ]) > long_absval(A[ I_B[i] ] - A[ I_B[j] ]))
        {
            res.insert(long_absval(B[ I_B[i] ] - B[ I_B[j] ]));
            // cerr << I_B[i] << ' ' << I_B[j] << ' ' << abs(B[ I_B[i] ] - B[ I_B[j] ]) << '\n';
        }
        nxt[i]++;
        compute_score_B(i);

        L.insert(loc{i, val[i]});
    }


    // cerr << "check3\n";



    int ct = 0;
    for(long long r:res)
    {
        ct++;
        if(ct > K) break;
        cout << r << '\n';
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:123:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  123 |     while(res.size() < K)
      |           ~~~~~~~~~~~^~~
road_construction.cpp:180:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  180 |     while(res.size() < 2*K)
      |           ~~~~~~~~~~~^~~~~

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