Submission #432275

#	Time	Username	Problem	Language	Result	Execution time	Memory
432275		blue	Road Construction (JOI21_road_construction)	C++17	11 / 100	10051 ms	59524 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> nxtA, nxtB;
vector<long long> valA, valB;

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

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

    if(nxtB[i] <= N-1)
    {
        valB[i] = B[ I_B[nxtB[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;







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

    valA = vector<long long>(N, INF);
    for(int i = 0; i < N; i++)
    {
        compute_score_A(i);
    }
    set<loc> LA;
    for(int i = 0; i < N; i++) LA.insert(loc{i, valA[i]});









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

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

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






    while(res.size() < K)
    {
        if(valA[LA.begin()->i] < valB[LB.begin()->i])
        {
            int i = LA.begin()->i;

            LA.erase(LA.begin());

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

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

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

            if(j > N-1) break;

            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';
            }
            nxtA[i]++;
            compute_score_A(i);

            LA.insert(loc{i, valA[i]});
        }
        else
        {
            int i = LB.begin()->i;

            LB.erase(LB.begin());

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

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

            if(j > N-1) 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';
            }
            nxtB[i]++;
            compute_score_B(i);

            LB.insert(loc{i, valB[i]});
        }
    }







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

/* Version 1


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

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

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

++++

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

    LA.erase(LA.begin());

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

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

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

    if(j > N-1) break;

    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';
    }
    nxtA[i]++;
    compute_score_A(i);

    LA.insert(loc{i, valA[i]});
}












// cerr << "switching \n";





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

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

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


++++++++++++

// cerr << "hello\n";

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

    LB.erase(LB.begin());

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

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

    if(j > N-1) 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';
    }
    nxtB[i]++;
    compute_score_B(i);

    LB.insert(loc{i, valB[i]});
}




*/

Compilation message (stderr)

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

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